// Source : https://leetcode.com/problems/maximum-subarray/
// Author : weekend27
// Date   : 2015-12-20

/**********************************************************************************

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.

click to show more practice.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

**********************************************************************************/

// How to do it:
// divide and conquer
/*
subarray A[i,..j] is
(1) Entirely in A[low,mid-1]
(2) Entirely in A[mid+1,high]
(3) Across mid
*/

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int maxV = INT_MIN;
        return maxArray(nums, 0, n-1, maxV);
    }

    int maxArray(vector<int>& nums, int left, int right, int& maxV){
        if (left > right){
            return INT_MIN;
        }

        int mid = left + (right - left) / 2;
        int lmax = maxArray(nums, left, mid-1, maxV);
        int rmax = maxArray(nums, mid+1, right, maxV);
        maxV = max(lmax, maxV);
        maxV = max(rmax, maxV);

        int lsum = 0;
        int mlmax = 0;
        for (int i = mid-1; i >= left; i--){
            lsum += nums[i];
            if (lsum > mlmax){
                mlmax = lsum;
            }
        }

        int rsum = 0;
        int mrmax = 0;
        for (int i = mid+1; i <= right; i++){
            rsum += nums[i];
            if (rsum > mrmax){
                mrmax = rsum;
            }
        }

        maxV = max(maxV, mlmax + mrmax + nums[mid]);
        return maxV;
    }
};