@@ -0,0 +1,1570 @@
+package MaximumSubarray;%0A%0A/**%0A * User: Danyang%0A * Date: 1/22/2015%0A * Time: 20:49%0A *%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 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%0A */%0Apublic class Solution %7B%0A    /**%0A     * O(n) iterative is trivial%0A     * Divide and Conquer Approach%0A     * O(n lgn)%0A     * 1. divide in half%0A     * 2. left max sub%0A     * 3. right max sub%0A     * 4. max sub crossing the middle point%0A     * @param A%0A     * @return%0A     */%0A    public int maxSubArray(int%5B%5D A) %7B%0A        return maxSubArray(A, 0, A.length);%0A    %7D%0A%0A    int maxSubArray(int%5B%5D A, int s, int e) %7B%0A        if(s%3E=e)%0A            return Integer.MIN_VALUE;%0A        if(s==e-1)%0A            return A%5Bs%5D;%0A%0A        int m = (s+e)/2;%0A        int l = maxSubArray(A, s, m);%0A        int r = maxSubArray(A, m, e);%0A        int c = maxCross(A, s, e, m);%0A        return Math.max(Math.max(l, r), c);%0A    %7D%0A%0A    int maxCross(int%5B%5D A, int s, int e, int m) %7B%0A        int max_l = A%5Bm%5D;%0A        int max_r = A%5Bm%5D;%0A%0A        int acc = A%5Bm%5D;%0A        for(int i=m-1; i%3E=s; i--) %7B%0A            acc += A%5Bi%5D;%0A            max_l = Math.max(max_l, acc);%0A        %7D%0A        acc = A%5Bm%5D;%0A        for(int i=m+1; i%3Ce; i++) %7B%0A            acc += A%5Bi%5D;%0A            max_r = Math.max(max_r, acc);%0A        %7D%0A        return max_l+max_r-A%5Bm%5D;%0A    %7D%0A%7D

Divide and Conquer Approach for Max Subarray Problem