动态规划

April 14, 2024 11:22 PM (GMT+8)

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

April 20, 2024 11:49 PM (GMT+8)

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

贪心

当前 sum 为负数的时候立刻舍弃，从下一个元素重新计算“连续和”

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0, res = INT_MIN;
        for (int x : nums) {
            sum +=x;
            res = max(res, sum);
            if (sum < 0) sum = 0; // greedy
        } 
        return res;
    }
};

分治法求解