Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

题意

求一个数组子数组最大和。

思路

判断状态数组的前一位是否大于0，是则加上当前位数字，更新状态，不是则把状态数组当前位设为当前数字。

代码

class Solution:
    def maxSubArray(self, nums):
        if len(nums) < 1:
            return 0
        dp = [0] * len(nums)
        dp[0] = nums[0]
        max_sum = nums[0]

        for i in range(1, len(nums)):
            if dp[i - 1] > 0:
                dp[i] = dp[i - 1] + nums[i]
            else:
                dp[i] = nums[i]
            max_sum = max(max_sum, dp[i])
        return max_sum