面試題 16.17. 連續數列

面試題 16.17. 連續數列 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxvalue(nums,0,nums.size()-1);
    }

    int maxvalue(vector<int>&nums,int l,int r){
        if(l==r) return nums[l];
        int mid=(l+r)/2;
        int maxv=INT32_MIN;
        int left=maxvalue(nums,l,mid);
        int right=maxvalue(nums,mid+1,r);
        int midlv=INT32_MIN,midrv=INT32_MIN;
        int suml=0,sumr=0;
        for(int i=mid;i>=l;i--){
            suml+=nums[i];
            if(suml>midlv) midlv=suml;
        }
        for(int i=mid+1;i<=r;i++){
            sumr+=nums[i];
            if(sumr>midrv) midrv=sumr;
        }
        maxv=max(left,right);
        maxv=max(maxv,midlv+midrv);
        return maxv;
    }
};