最大子数组和

1、题目

image-20240303230430889

2、题解

动态规划

第一步需要理解题意，找出最大连续子数组和，连续是一个关键点。题目只要求返回结果，不要求得到最大的连续子数组，可以用动态规划来解决。

第二步是如何定义子问题，根据不确定因素来清楚的定义子问题，从而让复杂的问题简单化。

首先无法知道最大的连续子数组一定会有某个数，因此可以求出所有经过输入数组的某一个数的连续子数组的最大和，例如输入数组为\([-2,1,-3,4,-1,2,1,-5,4]\)：

• 经过\(-2\)的连续子数组的最大和是多少
• 经过\(1\)的连续子数组的最大和是多少
• ……

上述各个子问题之间的联系很难看出，同时在子问题中无法确定每个数在自己的连续子数组中是第几个元素，不如将子问题定义为：

• 以\(-2\)结尾的连续子数组的最大和是多少
• 以\(1\)结尾的连续子数组的最大和是多少
• ……

以子问题\(1，2\)为例，问题\(1\)的答案就是\([-2]\),问题2的答案有\([-2,1],[1]\)，其中\([-2,1]\)就是在问题\(1\)的后面加上\(1\)得到的。\(-2+1=-1<1\),因此问题\(2\)的答案为\([1]\)。

从上述例子中可以看出如果问题i的结果是负数或者\(0\)，那么问题\(i+1\)的结果就可以把问题\(i\)的结果舍弃。

第三步定义子问题，\(dp[i]:\)表示以\(nums[i]\)​结尾的连续子数组的最大和。

状态转移方程1：

假设数组\(nums\)的值全都严格大于0，那么一定有\(dp[i]=dp[i-1]+nums[i]\)。当\(nums\)中存在负数时，\(dp[i-1]\)就可能为负数，那么\(nums[i]\)加上前面的\(dp[i-1]\)以后值不会变大，此时\(dp[i]\)就等于\(nums[i]\) \[ dp[i]=\begin{cases}dp[i-1]+nums[i],&if&dp[i-1]>0\\nums[i],&if&dp[i-1]\leq0\end{cases} \] 由于题目只是求最大值，并且只有两种情况，因此状态转移方程还可以写成： \[ dp[i]=\max\{nums[i],dp[i-1]+nums[i]\} \] 第四步规定初始值和输出，\(dp[0]=nums[0]\)。输出是所有\(dp\)值中的最大值，不是直接将最后一个状态返回出去

#状态转移方程1
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        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)

#状态转移方程2
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        pre = 0
        res = nums[0]

        for i in range(n):
            pre = max(nums[i], pre+nums[i])
            res = max(res,pre)

        return res