动态规划

    1. # 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
    2. #
    3. # 示例:
    4. #
    5. # 输入: [-2,1,-3,4,-1,2,1,-5,4]
    6. # 输出: 6
    7. # 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
    8. #
    9. #
    10. # 进阶:
    11. #
    12. # 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
    13. # Related Topics 数组 分治算法 动态规划
    14. # 👍 2303 👎 0
    15. # leetcode submit region begin(Prohibit modification and deletion)
    16. class Solution(object):
    17. def maxSubArray(self, nums):
    18. """
    19. :type nums: List[int]
    20. :rtype: int
    21. """
    22. for i in range(1, len(nums)):
    23. if nums[i - 1] > 0:
    24. nums[i] += nums[i - 1]
    25. return max(nums)
    26. # leetcode submit region end(Prohibit modification and deletion)
    27. s = Solution()
    28. print(s.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))