53. 最大子数组和

解题思路：

动态规划是本题的最优解法，以下按照标准流程解题。

动态规划解析：

• 状态定义： 设动态规划列表 $dp$ ，$dp[i]$ 代表以元素 $nums[i]$ 为结尾的连续子数组最大和。

  • 为何定义最大和 $dp[i]$ 中必须包含元素 $nums[i]$ ：保证 $dp[i]$ 递推到 $dp[i+1]$ 的正确性；如果不包含 $nums[i]$ ，递推时则不满足题目的 连续子数组 要求。

• 转移方程： 若 $dp[i-1] \leq 0$ ，说明 $dp[i - 1]$ 对 $dp[i]$ 产生负贡献，即 $dp[i-1] + nums[i]$ 还不如 $nums[i]$ 本身大。

$$ dp[i] = \begin{cases} dp[i-1] + nums[i] & , dp[i - 1] > 0 \ nums[i] & , dp[i - 1] \leq 0 \ \end{cases} $$

• 初始状态： $dp[0] = nums[0]$，即以 $nums[0]$ 结尾的连续子数组最大和为 $nums[0]$ 。

• 返回值： 返回 $dp$ 列表中的最大值，代表全局最大值。

{:width=500}

状态压缩：

• 由于 $dp[i]$ 只与 $dp[i-1]$ 和 $nums[i]$ 有关系，因此可以将原数组 $nums$ 用作 $dp$ 列表，即直接在 $nums$ 上修改即可。
• 由于省去 $dp$ 列表使用的额外空间，因此空间复杂度从 $O(N)$ 降至 $O(1)$ 。

<,,,,,,,,,>

代码：

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

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            if (nums[i - 1] > 0) nums[i] += nums[i - 1];
            if (nums[i] > res) res = nums[i];
        }
        return res;  
    }
};

复杂度分析：

• 时间复杂度 $O(N)$ ： 线性遍历数组 $nums$ 即可获得结果，使用 $O(N)$ 时间。
• 空间复杂度 $O(1)$ ： 使用常数大小的额外空间。