題目描述：
輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。
求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。
思路：
我們可以使用分治法或者減治法來(lái)處理這個(gè)問(wèn)題。
分治法
目標(biāo)：把1個(gè)大問(wèn)題分成2個(gè)小問(wèn)題，2個(gè)小問(wèn)題還可以再分，直到問(wèn)題規(guī)模小的可以簡(jiǎn)單解決。
將該數(shù)組等分成兩個(gè)子數(shù)組，假如知道左右兩側(cè)兩個(gè)數(shù)組的各自的最大子數(shù)組和，那么整個(gè)數(shù)組的最大子數(shù)組和可能為三種情況：
- 右側(cè)數(shù)組的最大子數(shù)組和
- 左側(cè)數(shù)組的最大子數(shù)組和
- 左右兩側(cè)數(shù)組中間毗鄰位置連接形成的子數(shù)組的和的最大值（如-6，4，-3，2####5，-6，9，-8，左側(cè)最大值為4，右側(cè)為9，中間毗鄰位置從2和5向兩側(cè)相加，得到中間毗鄰子數(shù)組4，-3，2，5，-6，9和為11，三者比較得最大子數(shù)組和為11）。
遞歸到數(shù)組中只包含一個(gè)數(shù)字。
這種思路也是可行的。進(jìn)行l(wèi)n(n)次拆分，每次拆分后進(jìn)行n次比較，所以算法復(fù)雜度為n*ln(n)。但還達(dá)不到題目的要求。
java代碼：
1 package com.island.info;
2 /**
3 * <p>Title: TestMaxArray.java</p>
4 * <p>Description: 分治法求解連續(xù)和最大</p>
5 * @date 2014-3-05
6 *
7 */
8
9 public class MaxSub {
10 static int arr[] = {4,-3,5,-2,-1,2,6,-2}; //也可以隨機(jī)生成
11 public static void main(String args[]){
12 System.out.println(max(arr));
13 }
14
15 //包裝函數(shù)
16 public static int max(final int[] arr){
17 System.out.println("(1)*****arr.length-1----------------->:"+ (arr.length-1));
18 return max(arr,0,arr.length-1);
19 }
20
21 //核心代碼：遞歸調(diào)用max()
22 public static int max(final int[] arr,int leftIndex, int rightIndex){
23 System.out.println("(2)*****leftIndex--------rightIndex--->:"+leftIndex+"|***************|"+rightIndex);
24 int sum = 0,leftHalfMax = 0, rightHalfMax = 0;
25 if (rightIndex-leftIndex==0){
26 return arr[rightIndex];
27 } else {
28 int center = (leftIndex+rightIndex)/2;//2分查找中間節(jié)點(diǎn)
29 int maxLeft = max(arr,leftIndex,center);//左邊最大的
30 int maxRight = max(arr,center+1,rightIndex);//右邊最大的
31 //以下是查找跨越中間點(diǎn)的最大子序列
32 //從中點(diǎn)到左側(cè)：
33 for (int i=center;i>=leftIndex;--i){
34 sum+=arr[i];
35 if (sum>leftHalfMax){
36 leftHalfMax = sum;
37 }
38 }
39 System.out.println("左邊的sum----------->:"+sum);
40 sum=0;
41 //從中點(diǎn)到右側(cè)
42 for (int i=center+1;i<=rightIndex;++i){
43 sum+=arr[i];
44 if (sum>rightHalfMax){
45 rightHalfMax = sum;
46 }
47 }
48 System.out.println("右邊的sum----------->:"+sum);
49 return max(maxLeft,maxRight,leftHalfMax+rightHalfMax);
50 }
51 }
52
53 //三者取最大值
54 public static int max(int a,int b,int c){
55 return a>b?(a>c?a:c):(b>c?b:c);
56 }
57 }
減治法
目標(biāo)：將問(wèn)題規(guī)模不斷減小，直到可以簡(jiǎn)單處理為止。
假設(shè)我們已知一個(gè)數(shù)組的最大子數(shù)組和，現(xiàn)在在該數(shù)組后面增加一個(gè)數(shù)字，新數(shù)組的最大子數(shù)組和可能是什么呢：
- 原數(shù)組的最大子數(shù)組和；
- 新增加的數(shù)字為正數(shù)，和最右側(cè)的子數(shù)組形成了一個(gè)新的最大子數(shù)組和（所以為了通過(guò)一次遍歷完成，我們需要保存最右側(cè)的子數(shù)組的最大和）。
然后將兩個(gè)數(shù)字進(jìn)行比較即可。
所以減治至數(shù)組只包含最左側(cè)一個(gè)數(shù)字，我們知道它的最大子數(shù)組和和最右側(cè)子數(shù)組最大和都為還數(shù)字，逐次加1個(gè)數(shù)字直到整個(gè)數(shù)組即可。
java代碼：
1 package com.island.info;
2
3 /**
4 * <p>Title: TestMaxArray.java</p>
5 * <p>Description: 分治法求解連續(xù)和最大</p>
6 * @date 2014-3-05
7 *
8 */
9 public class MaxSubArraySum {
10
11 private static long getMax(long a, long b) {
12 return a > b ? a : b;
13 }
14
15 /**
16 * 獲得連續(xù)子數(shù)組的最大和
17 * @param array
18 * @return 最大和，此處用了Long型是為了表示當(dāng)參數(shù)為null或空時(shí)，可以返回null，返回其它任何數(shù)字都可能引起歧義。
19 */
20
21 public static Long getMax(int[] array) {
22
23 if (array == null || array.length <= 0) {
24 return null;
25 }
26
27 long maxSum = array[0]; //所有子數(shù)組中最大的和
28 long righteEdge = array[0]; //右側(cè)子數(shù)組的最大和
29 for (int i = 1; i < array.length; i++) {
30 //當(dāng)右側(cè)子數(shù)組的最大和為負(fù)數(shù)時(shí)，對(duì)于新數(shù)組，右側(cè)子數(shù)組的最大和為新增加的數(shù)。
31 if (righteEdge < 0) {
32 righteEdge = array[i];
33 } else { //為正數(shù)時(shí)，對(duì)于新數(shù)組，右側(cè)子數(shù)組的最大和為新增加的數(shù) + 原來(lái)的最大和。
34 righteEdge += array[i];
35 }
36 //所有子數(shù)組中最大的和
37 System.out.println("righteEdge-------------maxSum:"+righteEdge+"****************"+maxSum);
38 maxSum = getMax(righteEdge, maxSum);
39 }
40 return maxSum;
41 }
42
43 public static void main(String[] args) {
44 int[] array = {1, -2, 3, 10, -4, 7, 2, -5};
45 //int arr[] = {4,-3,5,-2,-1,2,6,-2};
46 System.out.println("Max sum: " + MaxSubArraySum.getMax(array));
47 }
48
49 }