If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

https://oj.leetcode.com/problems/maximum-subarray/

思路1：Kadane算法，复杂度O(n)。

思路2：分治。对于每次递归，将数组分半，最大和可能存在

1. 完全在左面部分（递归求解）
   
2. 完全在右面部分（递归求解）
3. 横跨左右两个部分（从中间(必须包含中间元素，否则左右无法连接)向两边加，记录最大值）
   

注意点：注意负数的处理，此题最大值为负数时依然返回最大的负数，也有题目负数时要求返回0。注意两种情况下最大值的初始化等细节的区别。

思路1代码：

public class Solution {	public int maxSubArray(int[] A) {		int n = A.length;		int i;		int maxSum = A[0];		int thisSum = 0;		for (i = 0; i < n; i++) {			thisSum += A[i];			if (thisSum > maxSum)				maxSum = thisSum;			if (thisSum < 0)				thisSum = 0;		}		return maxSum;	}	public static void main(String[] args) {		System.out.println(new Solution().maxSubArray(new int[] { -2, 1, -3, 4,				-1, 2, 1, -5, 4 }));	}}

思路2代码：

public class Solution {    public int maxSubArray(int[] A) {        return maxSub(A, 0, A.length - 1);    }    private int maxSub(int[] a, int left, int right) {        if (left == right)            return a[left];        int mid = (left + right) / 2;        int maxLeft = maxSub(a, left, mid);        int maxRight = maxSub(a, mid + 1, right);        int leftHalf = 0, leftHalfMax = Integer.MIN_VALUE;        int rightHalf = 0, rightHalfMax = Integer.MIN_VALUE;        for (int i = mid; i >= left; i--) {            leftHalf += a[i];            if (leftHalf > leftHalfMax)                leftHalfMax = leftHalf;        }        for (int i = mid + 1; i <= right; i++) {            rightHalf += a[i];            if (rightHalf > rightHalfMax)                rightHalfMax = rightHalf;        }        return Math.max(Math.max(maxLeft, maxRight), (leftHalfMax + rightHalfMax));    }    public static void main(String[] args) {        System.out.println(new Solution().maxSubArray(new int[] { -2, -1, -3, -2, -5 }));    }}

Data Structures and Algorithm Analysis in C

http://blog.csdn.net/xshengh/article/details/12708291