【leetcode】53. 最大子数组和（python）动态规划

推荐学习大佬题解【经典动态规划问题（理解「无后效性」）】

思路分析：

    以nums[i]结尾的连续子数组的最大和是多少？
    nums[0]: f(0) = -2, cur_max_sum = -2  # 初始
    nums[1]: f(1)= max((-2) + 1, 1) = max(-1, 1) = 1, cur_max_sum = 1
    nums[2]: f(2)= max(f(1) + (-3), -3) = max(-2, -3) = -2, cur_max_sum = -2
    nums[3]: f(3)= max(f(2) + 4, 4) = max(2, 4) = 4, cur_max_sum = 4
    nums[4]: f(4)= max(f(3) + -1, -1) = max(3, -1) = 3, cur_max_sum = 3
    nums[5]: f(5)= max(f(4) + 2, 2) = max(5, 2) = 5, cur_max_sum = 5
    nums[6]: f(6)= max(f(5) + 1, 1) = max(6, 1) = 6, cur_max_sum = 6
    nums[7]: f(7)= max(f(6) + (-5), -5) = max(1, -5) = 1, cur_max_sum = 1
    nums[8]: f(8)= max(f(7) + 4, 4) = max(5, 4) = 5, cur_max_sum = 5
    总的再取最大和 ==> 6
    转移方程：f(i) = max(f(i-1) + nums[i], nums[i])
    result = max(f(0), f(1), f(2), f(3), ...)

写法一：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0 for i in range(n)]
        dp[0] = nums[0]
        max_sum = nums[0]
        for i in range(1, n):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
            if dp[i] > max_sum:
                max_sum = dp[i]
        return max_sum

写法二：

class Solution(object):
    def maxSubArray(self, nums):
        size = len(nums)
        if size == 0:
            return 0
        dp = [0 for _ in range(size)]
        dp[0] = nums[0]
        for i in range(1, size):
            if dp[i - 1] >= 0:
                dp[i] = dp[i - 1] + nums[i]
            else:
                dp[i] = nums[i]
        return max(dp)