Cacher is the code snippet organizer for pro developers

/*
Time complexity : o(n)
Note:
1. int res = Integer.MIN_VALUE; or int res = nums[0];都可以，没有overflow
2. 考虑edge case [-2, -1]: 
    res = Math.max(res, sum);不能只放在if里面
*/

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int sum = 0;
        // int res = Integer.MIN_VALUE; wrong
        int res = nums[0];
        for(int i = 0; i < nums.length; i++) {
            // sum = Math.max(nums[i], sum + nums[i]);
            if(sum >= 0)
                sum += nums[i];
            else 
                sum = nums[i];
            res = Math.max(res, sum);
        }
        return res;
    }
}

/*
Time complexity : o(nlogn)
分治法注意边界条件
-2
-2 1
-2 1 3


The worst case is 0. do not sum the element to the left. it is imopossible to be negative value
  int midLeftMax = 0;
  int midRightMax = 0;
*/

class Solution {
    public int maxSubArray(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }
    
    
    private int helper(int[] nums, int left, int right) {
        //boundary
        if(left == right)    return nums[left];
        if(left > right)    return Integer.MIN_VALUE;
        
        int mid = left + (right - left) / 2;
        
        int leftSum  = helper(nums, left, mid - 1);
        int rightSum = helper(nums, mid + 1, right);
        int crossSum = crossSum(nums, left, right, mid);
        
        return Math.max(Math.max(leftSum, rightSum), crossSum);
    }

    
    private int crossSum(int[] nums, int left, int right, int mid) {
        //boundary
        if(left == right)   return nums[left];
        
        //The worst case is 0. do not sum the element to the left.
        // it is imopossible to be negative value
        int midLeftMax = 0;
        int midRightMax = 0;
        int currentSum = 0;
            
        for(int i = mid - 1; i >= left; i--) {
            currentSum += nums[i];
            midLeftMax = Math.max(midLeftMax, currentSum);
        }
        
        currentSum = 0;
        for(int i = mid + 1; i <= right; i++) {
            currentSum += nums[i];
            midRightMax = Math.max(midRightMax, currentSum);
        }
        
        return midLeftMax + nums[mid] + midRightMax;
    }
    
}