题目描述

blablabla

样例

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[i] = max(0, dp[i - 1]) + nums[i];

C++ 代码

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;
    }
};