/**
 *	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.
 *
 *	Author: matao	
 *
 */

public class MaximumSubarray {

	// sliding window 滑动窗口
	public static int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int maxSub = nums[0], max = nums[0];
        for (int i = 1; i < nums.length; i++) {
        	if(max < 0) {
        		max = 0;
        	}
        	max += nums[i];
        	if(max > maxSub) {
        		maxSub = max;
        	}
        }
        return maxSub;
    }

	public static void main(String[] args) {
		int[] nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
		System.out.println(maxSubArray(nums1));
	}
}
@@ -297,17 +297,17 @@
 %09// 
-s
+S
 liding 
-w
+W
 indo
@@ -343,16 +343,17 @@
 SubArray
+1
 (int%5B%5D n
@@ -712,16 +712,1169 @@
 %0A    %7D%0A%0A
+    // Divide & Conquer%0A    public static int maxSubArray2(int%5B%5D nums) %7B%0A    %09if(nums == null %7C%7C nums.length == 0) %7B%0A    %09%09return 0;%0A    %09%7D%0A    %09return maxSubArrayHelper(nums, 0, nums.length - 1);%0A    %7D%0A%0A    private static int maxSubArrayHelper(int%5B%5D nums, int left, int right) %7B%0A    %09if(left == right) %7B%0A    %09%09return nums%5Bleft%5D;%0A    %09%7D%0A%0A    %09int mid = left + (right - left) / 2;%0A    %09int maxLeft = maxSubArrayHelper(nums, left, mid);%0A    %09int maxRight = maxSubArrayHelper(nums, mid + 1, right);%0A%0A    %09// %E5%A6%82%E6%9E%9C%E6%9C%80%E5%A4%A7%E5%80%BC%E8%B7%A8%E8%BF%87mid%EF%BC%8C%E9%83%A8%E5%88%86%E5%B7%A6%E8%BE%B9%EF%BC%8C%E9%83%A8%E5%88%86%E5%8F%B3%E8%BE%B9%0A    %09int maxTempLeft = nums%5Bmid%5D, sumTempLeft = nums%5Bmid%5D;%0A    %09for(int i = mid - 1; i %3E= left; i--) %7B%0A    %09%09sumTempLeft += nums%5Bi%5D;%0A    %09%09if(maxTempLeft %3C sumTempLeft) %7B%0A    %09%09%09maxTempLeft = sumTempLeft;%0A    %09%09%7D%0A    %09%7D%0A    %09int maxTempRight = nums%5Bmid + 1%5D, sumTempRight = nums%5Bmid + 1%5D;%0A    %09for(int j = mid + 2; j %3C= right; j++) %7B%0A    %09%09sumTempRight += nums%5Bj%5D;%0A    %09%09if(maxTempRight %3C sumTempRight) %7B%0A    %09%09%09maxTempRight = sumTempRight;%0A    %09%09%7D%0A    %09%7D%0A    %09int maxMid = maxTempLeft + maxTempRight;%0A%0A    %09return (maxLeft %3E maxRight ? maxLeft : maxRight) %3E maxMid ? (maxLeft %3E maxRight ? maxLeft : maxRight) : maxMid;%0A    %7D%0A%0A
 %09public 
@@ -1956,16 +1956,60 @@
 -5, 4%7D;%0A
+%09%09int%5B%5D nums2 = %7B2, 0, -3, 2, 1, 0, 1, -2%7D;%0A
 %09%09System
@@ -2032,16 +2032,17 @@
 SubArray
+1
 (nums1))
@@ -2043,12 +2043,141 @@
 ums1));%0A
+%09%09System.out.println(maxSubArray2(nums1));%0A%09%09System.out.println(maxSubArray1(nums2));%0A%09%09System.out.println(maxSubArray2(nums2));%0A
 %09%7D%0A%7D

add divide&conquer solution