[LeetCode 53] Maximum Subarray (

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

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

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        
        
        // Solution 1: 当sum为负数时，不管后面是正是负，基于负数的累加只可能小。所以一旦sum为负数时，就要移动start，直到sum为正或者start > end
        /*
        int start = 0;
        int end = 0;
        int max = nums[0];
        int adds = 0;
        
        while (end < nums.length) {
            adds += nums[end];
            max = Math.max (max, adds);
            
            while (adds < 0 && start <= end) {
                adds -= nums[start];
                start ++;
            }
            
            end ++;
        }
        
        return max;
        */
        
        //Solution2： O(n), 只扫描一遍，需两个变量，maxToCurrent = max (maxToCurrent + nums[index], nums[index])
        // 记录的是到当前num，当前最大的sum （因为取得的是二者最大值，如果之前的maxToCurrent为负，maxToCurrent就会被忽略掉）
        // 所以maxToCurrent一定是，走到当前num时，局部最大值。
        // 同时还需要：max = max (max, maxToCurrent)
        
        /*
        int maxToCurrent = nums[0];
        int max = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            maxToCurrent = Math.max (maxToCurrent + nums[i], nums[i]);
            max = Math.max (max, maxToCurrent);
        }
        
        return max;
        */
        
        // Solution3: divide and conquer
        return helper (nums, 0, nums.length - 1);
    }
    
    public int helper (int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        
        if (start > end) {
            return Integer.MIN_VALUE;
        }
        
        int middle = start + (end - start) / 2;
        int left = helper (nums, start, middle - 1);
        int right = helper (nums, middle + 1, end);
        int toLeft = 0;
        int toRight = 0;
        
        int sum = 0;
        for (int i = middle - 1; i >= start; i--) {
            sum += nums[i];
            
            if (sum > toLeft) {
                toLeft = sum;
            }
        }
        
        sum = 0;
        for (int i = middle + 1; i <= end; i++) {
            sum += nums[i];
            
            if (sum > toRight) {
                toRight = sum;
            }
        }
        
        
        return Math.max (Math.max (left, right), toLeft + nums[middle] + toRight);
    }
}