53. 最大子数组和

链接

https://leetcode.cn/problems/maximum-subarray/description/

思路

1. 在线处理法：对于一个连续的序列来说，如果它小于0，那么它对于周围所有的数组都是减益效果。试想一下，任何数与负数相加，都小于它本身。根据此，可以用在线处理法，O(n)的时间即可搞定。

2. 动态规划法：这个题存在中间状态可以被dp存储。（但没必要，在线处理其实就是O(1)的dp）。设dp[i]表示以i下标结尾的数组最大和。那么我们能够得到状态转移方程为：

dp[i] = max(dp[i-1]+nums[i], nums[i]). 

代码-在线处理

class Solution:
    def maxSubArray(self, nums) -> int:
        res = nums[0]
        cur_res = 0
        for i in nums:
            cur_res += i
            res = max(cur_res, res)
            if cur_res < 0:
                cur_res = 0
        return res

代码-动态规划

class Solution:
    def maxSubArray(self, nums) -> int:
        dp = nums[:]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        return max(dp)