[LeetCode] Maximum Subarray

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.

 解体思路：
       1. 数组A[0..j]的最大和来自于子数组A[0..j-1]或者来自于A[i..j]
       2. 对于A[i..j]的最大数，是 A[i..j-1]+A[j] or A[j]
       3. 使用divide-conquer 解法：A[0..n]的最大值来自于3个地方：左边子数组A[0..j]， 右边子数组 A[j+1..n]的最大值，或者跨越这两个数组之间的最大值，也就是一定包含A[j],A[j+1]的最大值。
     
     

public int maxSubArray(int[] A) {
        if(A.length == 0) return 0;
        int maxSum = A[0];
        int sum = A[0];
        
        for(int i = 1; i < A.length; i++){
           sum = A[i] > sum + A[i] ? A[i] : sum + A[i];
           maxSum = Math.max(maxSum, sum);
        }
     
        return maxSum;
    }

divide-conquer的解法

public int maxSubArray(int[] A) {
        if (A.length == 0) return 0;
        
        return maxSubarray(A, 0, A.length - 1);
    }

    public int maxSubarray(int[] A, int start, int end) {
        int mid = (start + end) / 2;
        int leftMax = Integer.MIN_VALUE;
        int rightMax = Integer.MIN_VALUE;
        int crossMax = Integer.MIN_VALUE;
        int maxSum = 0;
        
        if(start == end) return A[start];
        
        if (mid >= start) {
            leftMax = maxSubarray(A, start, mid);
        }

        if (mid < end) {
            rightMax = maxSubarray(A, mid + 1, end);
        }


        if (mid >= start && mid < end) {
            int sum = A[mid];
            crossMax = A[mid];
            
            for (int j = mid - 1; j >= start; j--) {
                sum += A[j];
                crossMax = Math.max(sum, crossMax);
            }

            crossMax+= A[mid+1];
            sum = crossMax;
            
            for (int i = mid + 2; i <= end; i++) {
                sum += A[i];
                crossMax = Math.max(sum, crossMax);
            }
        }
        
        maxSum = Math.max(leftMax,rightMax);
        maxSum = Math.max(maxSum, crossMax);
        
        return maxSum;
    }