最大子数组和

发表于 分类于 ， 阅读次数： Waline： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

53. 最大子数组和

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

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

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

输出：6

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

思路：

因为数组中存在负数，所以我们不能使用滑动窗口。

定义dp数组：以nums[i]为结尾的「最大数组和」为dp[i]

假设我们已经知道了dp[i-1]，那么如何推导得到dp[i]呢？

我们知道，dp[i]有两种选择，要么和前面的相邻子数组连接，形成一个更大的子数组，要么不与前面连接，自成一个子数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if( n == 0) return 0;
        //定义 dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
        vector<int> dp(n);
        //base case: 第一个元素前面没有子数组
        dp[0] = nums[0];
        //状态转移方程
        for(int i = 1; i < n; i++){
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
        }
        //得到 nums 的最大子数组
        int res = INT_MIN;
        for(int i = 0; i < n; i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};

从状态转移方程可以看出

1
dp[i] = max(nums[i], nums[i] + dp[i - 1])；

dp[i]只与dp[i-1]有关。所以我们可以进行状态压缩。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if( n == 0) return 0;
        // base case
        int dp_0 = nums[0];
        int dp_1 = 0, res = dp_0;

        for(int i = 1; i < n; i++){
            // dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            dp_1 = max(nums[i], nums[i] + dp_0);
            //保存dp_1 变成下一次开始前的 dp_0
            dp_0 = dp_1;
            //计算最大结果
            res = max(res, dp_1);
        }
        return res;
    }
};