Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array[-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

第一种解法：分治法

class Solution {
public:
    vector<int> findCrossSubArray(vector<int>& nums, int mid, int low ,int high){
        int sum = 0;
        int leftSum = INT_MIN;
        int maxLeft = 0;
        for (int i = mid; i>=low; i--) {
            sum = sum+nums[i];
            if (sum>leftSum) {
                leftSum = sum;
                maxLeft = i;
            }
        }
        sum = 0;
        int rightSum = INT_MIN;
        int maxRight = 0;
        for (int j=mid+1; j<=high; j++) {
            sum = sum+nums[j];
            if (sum>rightSum) {
                rightSum = sum;
                maxRight = j;
            }
        }
        
        return {{maxLeft,maxRight,leftSum+rightSum}};
    }

    vector<int> findMaxSubArray(vector<int>& nums,int low ,int high)
    {
        if (low==high) {
            return {{low,high,nums[low]}};
        }else{
            int mid = (low+high)/2;
            vector<int> leftSum = findMaxSubArray(nums, low, mid);
            vector<int> rightSum = findMaxSubArray(nums, mid+1, high);
            vector<int> crossSum = findCrossSubArray(nums, mid, low, high);
            if (leftSum[2]>=rightSum[2]&&leftSum[2]>=crossSum[2]) {
                return leftSum;
            }else if(rightSum[2]>=leftSum[2]&&rightSum[2]>=crossSum[2])
            {
                return rightSum;
            }
            else return crossSum;
        }
    
    }


    int maxSubArray(vector<int>& nums) {
        int len = nums.size()-1;
        vector<int> result = findMaxSubArray(nums, 0, len);
        return result[2];
    }
};

第二种解法：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans=nums[0],i,j,sum=0;
        for(i=0;i<nums.size();i++){
            sum+=nums[i];
            ans=max(sum,ans);
            sum=max(sum,0);
        }
        return ans;
    }
};