题目描述

blablabla

样例

blablabla

算法1

(动态规划) $O(n)$

C++ 代码

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