53. Maximum Subarray

class Solution {
    public int maxSubArray(int[] nums) {
        int[] maxSubArray = new int[nums.length];
        maxSubArray[0] = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxSubArray[i] = Math.max(nums[i], maxSubArray[i - 1] + nums[i]);
            maxSum = Math.max(maxSubArray[i], maxSum);
        }
        return maxSum;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int curMax = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curMax = Math.max(nums[i], curMax + nums[i]);
            maxSum = Math.max(curMax, maxSum);
        }
        return maxSum;
    }
}

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