參考鏈接：http://blog.csdn.net/butwang/article/details/4691974

思路：如果已經知道在前0~k-1共k個元素中，在最大和為MaxAll[k-1]， 怎么求0~k共k+1個元素的MaxAll[k]。 如果前k個元素的最大和子序列包括a[k-1]，則很容易知道MaxAll[k] = max(MaxAll[k-1] + a[k], a[k])。那如果前k個元素的最大和子序列不包括a[k-1]呢？在數組后面增加一個元素，會改變數組最后面子序列的和，因此MaxAll[k] = max(MaxAll[k-1], MaxAll[k-1] + a[k], a[k])。定義EndMax[k-1]為前k個元素中包括a[k-1]的最大子序列和。則遞推公式如下：

EndMax[k] = max(EndMax[k-1] + a[k], a[k])

MaxAll[k] = max(MaxAll[k-1], EndMax[k])

可以看出，沒有必要使用兩個數組，可以使用兩個變量取代MaxAll[k]和EndMax[k]。

代碼：

 1 package algorithm; 2  3 public class maxSubSum { 4     // 求一個數組中最大子序列的和 5     public static void main(String[] args) { 6         int a[] = { -3, 3, -1, 4, -2, -1 }; 7  8         int AllMax = a[0]; 9         int EndMax = a[0];10 11         int AllMaxStart = 0, AllMaxEnd = 0, EndMaxStart = 0, EndMaxEnd = 0;12 13         for (int i = 1; i < a.length; i++) {14             if (EndMax + a[i] > a[i]) {15                 EndMax = EndMax + a[i];16                 EndMaxEnd = i;17             } else {18                 EndMax = a[i];19                 EndMaxStart = i;20                 EndMaxEnd = i;21             }22             23             if (EndMax > AllMax) {24                 AllMax = EndMax;25                 AllMaxStart = EndMaxStart;26                 AllMaxEnd = EndMaxEnd;27             }28         }29         30         System.out.