一，問題描述
給定（可能有負數）整數a(1)、a(2)、……a(n)，求 a(1)+a(2)+……+a(j)的最大值。為友善起見，若所有的整數為負數，則最大子序列和為0.
也就是：在一系列整數中，找出連續的若幹個整數，這若幹個整數之和 最大。
二，求解思路
下面介紹兩種思路，一種的時間複雜度為O(N^3)，另一種為O(N)。這兩種方法分别類似于 在O(N)時間内求解 正數數組中 兩個數相加的 最大值 和 兩種方法求解 正數數組中 兩個數相減 的最大值
裡面介紹的O(N^2)算法和 O(N)算法。都是采用了“貪心”的思想 忽略掉某些不需要判斷的元素，如本文中算法二：總是選擇，使目前序列之和變成負數的下一個元素作為新的起點。
是以，可以看出，最大子序列和問題 其實 與尋找“正整數數組中兩個數相減的最大值” 、“正整數數組中兩個數相加的最大值”等問題很相似。
算法一如下：
分别用兩個下标 i , j 标記某個子序列的起點和終點。然後，從 i 周遊 到 j，求出[i,j]内所有元素的和，這個 和值 就是這一段子序列的和。
i belongs to [0, arr.length) , j belongs to [i, arr.length) 這樣，就代表了所有的子序列，再找出所有子序列和的最大值。
代碼如下：
1 public static int maxSubSum1(int[] arr) {
2 int maxSum = 0;
3
4 for (int i = 0; i < arr.length; i++)
5 for (int j = i; j < arr.length; j++) {
6 int thisSum = 0;
7 for (int k = i; k <= j; k++)
8 thisSum += arr[k];// 求解[i,j]這段子序列的和
9 if (thisSum > maxSum)
10 maxSum = thisSum;
11 }
12 return maxSum;
13 } 算法二如下：
算法二基于下面兩個事實：
①任何負的 子序列都不可能是最大子序列和 的字首
②當加上 下标 j 所在的元素 使得 目前序列的和變成負數時，根據①，可以從 j+1 處重新開始計算下一段子序列的和。
因為某段子序列到索引 j 位置時，它們的和是負的，意味着最大子序列不會 包含這一段子序列，那麼從 j+1 開始，能不能找到一段更大的子序列。
1 public static int maxSubSum2(int[] arr) {
2 int maxSum = 0;
3 int thisSum = 0;
4 for (int i = 0; i < arr.length; i++) {
5 thisSum += arr[i];
6 if (thisSum > maxSum)// thisSum在[0,maxSum]之間時不需要任何處理
7 maxSum = thisSum;
8 else if (thisSum < 0)// 說明加上目前元素使得子序列為負數了,那麼抛棄這段子序列(相當于thisSum指派為0),從下一輪for開始
9 thisSum = 0;
10 }
11 return maxSum;
12 } 三，運作時間的比較
采用 這篇文章 中提到的随機數生成算法 來随機生成一個數組，然後比較上面兩個算法的運作時間。
機器環境如下：
OS:win7 64bit、RAM:6GB、CPU:Pentium(R)Dual-Core [email protected]
時間比較如下：
數組大小 maxSubSum1運作時間(O(N)) maxSubSum2算法2運作時間(O(N^3))
100*10 0 95
200*10 0 647
300*10 0 2128
400*10 0 40246
這就是差距。。。。。。
完整程式代碼如下：
1 public class MaxSequence {
2
3 public static int maxSubSum1(int[] arr) {
4 int maxSum = 0;
5
6 for (int i = 0; i < arr.length; i++)
7 for (int j = i; j < arr.length; j++) {
8 int thisSum = 0;
9 for (int k = i; k <= j; k++)
10 thisSum += arr[k];// 求解[i,j]這段子序列的和
11 if (thisSum > maxSum)
12 maxSum = thisSum;
13 }
14 return maxSum;
15 }
16
17 public static int maxSubSum2(int[] arr) {
18 int maxSum = 0;
19 int thisSum = 0;
20 for (int i = 0; i < arr.length; i++) {
21 thisSum += arr[i];
22 if (thisSum > maxSum)// thisSum在[0,maxSum]之間時不需要任何處理
23 maxSum = thisSum;
24 else if (thisSum < 0)// 說明加上目前元素使得子序列為負數了,那麼抛棄這段子序列(相當于thisSum指派為0),從下一輪for開始
25 thisSum = 0;
26 }
27 return maxSum;
28 }
29
30 public static void main(String[] args) {
31 int[] arr = C2_2_8.randomArr(100*80);
32
33 long start = System.currentTimeMillis();
34 int r = maxSubSum2(arr);
35 long end = System.currentTimeMillis();
36 System.out.println("maxValue=" + r + " O(N)'s time:" + (end - start));
37
38 long start2 = System.currentTimeMillis();
39 int r2 = maxSubSum1(arr);
40 long end2 = System.currentTimeMillis();
41 System.out.println("maxValue=" + r2 + " O(N^3)'s time:"
42 + (end2 - start2));
43
44 }
45 }