连续子数组的最大和

ryluo 2020-07-23 17:53:22

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

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

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

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

样例

输入:[1, -2, 3, 10, -4, 7, 2, -5]

输出:18

最优解法(动态规划):

  1. 令dp[i]表示前i个数组中的子数组最大和
  2. 当dp[i-1] < 0时 dp[i] = nums[i], 当dp[i-1] > 0时 dp[i] = dp[i-1] + nums[i]
  3. 返回dp数组中的最大值

空间优化,可以通过一个变量不断更新最大值.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++){
            if(sum > 0) sum += nums[i];
            else sum = nums[i];

            res = max(res, sum);
        }

        return res;
    }
};