LeetCode-53 最大子数组和

题目描述

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/maximum-subarray

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。 

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 

题解

暴力法

• 第一层遍历更新起始位置
• 第二层求和寻找最大值

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sub = INT32_MIN;
        for(int i = 0; i < nums.size(); ++i) {
            int sub = 0;
            for(int j = i; j < nums.size(); ++j) {
                sub += nums[j];
                max_sub = sub > max_sub ? sub : max_sub;
            }
        }

        return max_sub;
    }
};

Name	Value
时间复杂度	$O(n^2)$
空间复杂度	$O(1)$

• 存在超时问题

贪心

当遍历到元素为负数时，连续和肯定在变小，贪心的局部最优则是当当前连续和为负数的时候，则放弃当前元素，从下一个元素继续计算连续和，因为当前元素为负数时，下一次相加的连续和只会变小

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sub = INT32_MIN;
        int sub = 0;
        for(int i = 0; i < nums.size(); ++i) {
            sub += nums[i];
            if(sub > max_sub) {
                max_sub = sub;
            }
            if(sub <= 0) {
                sub = 0;
            }
        }

        return max_sub;
    }
};

Name	Value
时间复杂度	$O(n)$
空间复杂度	$O(1)$

动态规划

用 $dp[i]$ 表示以 $nums[i]$ 结尾的最大子数组和，那么 $dp[i]$ 的状态转移有两种情况

1. 加入 $nums[i]$ 后子数组和变大 $dp[i] = dp[i-1] + nums[i]$
2. 从头计算子数组和 $dp[i] = nums[i]$

那么状态转移方程为

$$dp[i] = max\{dp[i-1] + nums[i],nums[i] \}$$

• $dp[0] = nums[0]$
• $dp[i]$ 的状态至只与 $dp[i-1]$ 相关，所以还需要创建一个 $max\_sub$ 来维护最大值

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

        return max_sub;
    }
};

Name	Value
时间复杂度	$O(n)$
空间复杂度	$O(n)$

用一个表格方便理解

input: nums = [-2,1,-3,4,-1,2,1,-5,4]

output: 6

连续子数组 [4,-1,2,1] 的和最大，为 6

i	0	1	2	3	4	5	6	7	8
nums[i]	-2	1	-3	4	-1	2	1	-5	4
dp[i]	-2	1 (-2, 1)	-2 (-2, -3)	4 (-2, 4)	3 (3, -1)	5 (5, 2)	6 (6, 1)	1 (1, -5)	5 (5, 4)
result	-2	1 (-2, 1)	1 (1, -2)	4 (4, 1)	4 (4, 3)	4 (5, 4)	6 (6, 5)	6 (6, 1)	6 (6, 5)

• 最终返回的 $max\_sub$ 即为最大子数组和

优化动态规划

由于 $dp[i]$ 只与 $dp[i-1]$ 相关，并且创建了 $max\_sub$ 来维护最大的和，所以可以优化 $dp[n]$ 为一个变量 $dp$ 即可

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp = 0;
        int max_sub = nums[0];
        
        for(const auto i : nums) {
            dp = max(dp + i, i);
            if(dp > max_sub) {
                max_sub = dp;
            }
        }

        return max_sub;
    }
};

Name	Value
时间复杂度	$O(n)$
空间复杂度	$O(1)$

用一个表格方便理解

input: nums = [-2,1,-3,4,-1,2,1,-5,4]

output: 6

连续子数组 [4,-1,2,1] 的和最大，为 6

i	0	1	2	3	4	5	6	7	8
nums[i]	-2	1	-3	4	-1	2	1	-5	4
dp	0	1 (1, 0)	-2 (-2, -3)	4 (-2, 4)	3 (3, -1)	5 (5, 2)	6 (6, 1)	1 (1, -5)	5 (5, 4)
result	-2	1 (-2, 1)	1 (1, -2)	4 (4, 1)	4 (4, 3)	4 (5, 4)	6 (6, 5)	6 (6, 1)	6 (6, 5)