数组最大连续和

LeetCode

给一个数组, 其中元素有正有负, 求数组的连续最大和.

最直观的暴力法可解. 但不可行. 用两个数记录当前和以及当前最大值, 当当前和《=0时, 将当前和重置.

int maxSubArray(vector<int>& nums) {
    if(nums.size()==0)
        return 0;
    if(nums.size()==1)
        return nums[1];
    int max_v = INT32_MIN;
    int cur_sum=0;
    for(int v: nums){
        if(cur_sum<=0)
            cur_sum=v;
        else{
            cur_sum+=v;
        }
        if(cur_sum>max_v)
            max_v=cur_sum;
    }
    return max_v;
}