53. 最大子序和

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

解法一：暴力

遍历所有长度的连续子段，but超时

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = -sys.maxsize
        for i in range(len(nums)):
            for j in range(i, -1, -1):
                res = max(res, sum(nums[j:i+1]))
        return res

解法二：dp

摘自《计算机算法设计与分析》王晓东 第3版

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sum = nums[0]  #初始累加和
        b = nums[0]  #dp初始状态，0号
        for i in range(1, len(nums)):  #从1号开始
            if b > 0:
                b += nums[i]
            else:
                b = nums[i]
            sum = max(b, sum)
        return sum

2020.3.29

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        res = nums[0]
        if n == 1:
            return res
        dp[0] = nums[0]    #初始
        #用dp[i]记录0~i处最大子序和（包括i）
        for i in range(1, n):
            if dp[i-1] < 0:    #若前面的和小于0，则舍弃
                dp[i] = nums[i]
            else:
                dp[i] = dp[i-1] + nums[i]
            res = max(res, dp[i])     #更新最大和
        return res

2021.10.13 nums[0..i] 中的「最大的子数组和」为 dp[i]。

问题：能用 dp[i] 推出 dp[i+1] 吗？（与300. 最长上升子序列的问题类似）

实际上是不行的，因为子数组一定是连续的，按照我们当前 dp 数组定义，并不能保证 nums[0..i] 中的最大子数组与 nums[i+1] 是相邻的，也就没办法从 dp[i] 推导出 dp[i+1]。

改进：以 nums[i] 为结尾的「最大子数组和」为 dp[i]。

class Solution:
    def maxSubArray(self, nums) -> int:
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        dp = [0] * n
        dp[0] = nums[0]  # 初始
        res = dp[0]

        for i in range(1, n):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
            res = max(res, dp[i])
        return res

改进：状态压缩 由于迭代过程中只用到dp[i-1]和dp[i]，用dp_0和dp_1代替节省空间

class Solution:
    def maxSubArray(self, nums) -> int:
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        dp = [0] * n
        dp_0 = nums[0]  # 初始
        res = dp_0

        for i in range(1, n):
            dp_1 = max(nums[i], dp_0 + nums[i])
            dp_0 = dp_1
            res = max(res, dp_0)
        return res