Skip to content
当前页大纲

解题思路:

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

常见解法时间复杂度空间复杂度
暴力搜索$O(N^2)$$O(1)$
分治思想$O(N \log N)$$O(\log N)$
动态规划$O(N)$$O(1)$

动态规划解析:

  • 状态定义: 设动态规划列表 $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$ 列表中的最大值,代表全局最大值。

Picture1.png

状态压缩:

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

<Picture2.png,Picture3.png,Picture4.png,Picture5.png,Picture6.png,Picture7.png,Picture8.png,Picture9.png,Picture10.png,Picture11.png>

代码:

Python
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)
Java
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;
    }
}
C++
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)$ : 使用常数大小的额外空间。

MIT License.