b089caea6ec24aca941d82facdc026a0.png

【题目】：53. 最大子数组和
方法1. 前缀和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int res = INT_MIN;
        int cur = 0;
        vector<int> preSum(n + 1, 0);
        for(int i = 0; i < n; ++i) {
            preSum[i + 1] = nums[i] + preSum[i];
        }
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j <= n; ++j) {
                res = max(res, preSum[j] - preSum[i]);
            }
        }
        return res;
    }
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n)

用preSum维护前缀和，然后循环preSum， preSum[j] - preSum[i]就是子数组i到j的和。但是这个方法会超时=。=

方法2. 动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = nums[0];
        vector<int> dp(nums.size(), 0); // dp[i]表示以 nums[i] 结尾的连续子数组的最大和
        dp[0] = nums[0];
        for(int i = 1; i < nums.size(); ++i) {
            // max(dp[i - 1] + nums[i], nums[i])
            dp[i] = max(dp[i - 1], 0) + nums[i];
            res = max(res, dp[i]);
        }
        return res;
    }
};

方法3. 

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int res = INT_MIN;
        for(int i = 0; i < nums.size(); ++i) {
            if(sum >= 0) { // 正数>>整数对结果是促进作用
                sum += nums[i];
            }else { // 负数>>负数对结果是抑制的作用，直接重新开始算
                sum = nums[i];
            }
            res = max(res, sum);
        }
        return res;
    }
};

如果sum是正数，说明sum + nums[i]对结果是促进作用；
如果sum是负数，说明sum + nums[i]对结果是抑制作用，直接丢弃前边累加的结果。