【剑指 offer】连续子数组的最大和

1、题目描述

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例

输入：[1, -2, 3, 10, -4, 7, 2, -5]
输出：18

2、问题描述：

3、问题关键：

• 连续子数组。
• 最大后缀和。
• dp[i] = max(0, dp[i - 1]) + nums[i];

4、C++代码：

算法 1:

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

算法2:（dp）

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