@@ -0,0 +1,1797 @@
+/***%0A * Find the contiguous subarray within an array (containing at least one number) which has the largest sum.%0A *%0A * For example, given the array %5B%E2%88%922,1,%E2%88%923,4,%E2%88%921,2,1,%E2%88%925,4%5D,%0A * the contiguous subarray %5B4,%E2%88%921,2,1%5D has the largest sum = 6.%0A *%0A * click to show more practice.%0A *%0A * More practice:%0A * If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.%0A */%0Apublic class Solution %7B%0A    // Solution 1: 1 d DP: O(n) O(1)%0A    /*%0A    public int maxSubArray(int%5B%5D A) %7B%0A        int local_max = A%5B0%5D;%0A        int global_max = A%5B0%5D;%0A%0A        for (int i = 1; i %3C A.length; i++) %7B%0A            local_max = local_max + A%5Bi%5D %3E A%5Bi%5D ? local_max + A%5Bi%5D : A%5Bi%5D;%0A            global_max = local_max %3E global_max ? local_max : global_max;%0A        %7D%0A        return global_max;%0A    %7D%0A    */%0A%0A    // Solution 2: divide and conquer, O(log n)%0A    public int maxSubArray(int%5B%5D A) %7B%0A        int maxV = Integer.MIN_VALUE;%0A        return maxSubArray(A, 0, A.length - 1, maxV);%0A    %7D%0A    private int maxSubArray(int A%5B%5D, int left, int right, int maxV) %7B%0A        if (left %3E right)%0A            return Integer.MIN_VALUE;%0A        int mid = (left + right) / 2;%0A        int lmax = maxSubArray(A, left, mid - 1, maxV);%0A        int rmax = maxSubArray(A, mid + 1, right, maxV);%0A        maxV = Math.max(maxV, lmax);%0A        maxV = Math.max(maxV, rmax);%0A        int local = 0, lm = 0;%0A        for (int i = mid - 1; i %3E= left; i--)%7B%0A            local = local + A%5Bi%5D;%0A            lm = Math.max(local, lm);%0A        %7D%0A        local = 0; %0A        int rm = 0;%0A        for (int i = mid + 1; i %3C= right; i++) %7B%0A            local = local + A%5Bi%5D;%0A            rm = Math.max(local, rm);%0A        %7D%0A        maxV = Math.max(maxV, lm + rm + A%5Bmid%5D);%0A        return maxV;%0A%0A    %7D%0A%7D%0A

add MaximumSubarray.java