演算法一：

思想分析：

要求解序列中最大的和，那麼需要得到，每個序列的和，並比較值

int[] a = {-1, 0, 1, 2, -3, 8, 6};

[-1]

[-1,0]

[-1,0,1]

...

[0]

[0,1]

[0,1,2]

...

這種演算法，時間複雜度O(N^3)

/**

* 求最大子序列和 解法一：

*/

public static void main(String[] args) {int[] a = {-1, 0, 1, 2, -3, 8, 6};int b = maxSum1(a);System.out.println(b);}

public static int maxSum1(int[] a) {int maxSum = 0;

for (int i = 0; i < a.length ; i++) { //迴圈大小為N

for (int j = i; j < a.length; j++) { //迴圈大小為 N-i

int thisSum = 0;

for (int k = i; k <= j ; k++) //迴圈大小為j -i + 1 (求和與比較放在一個迴圈也是ok的，這裡分開了，只求和)

thisSum += a[k];

if (thisSum > maxSum) {maxSum = thisSum;}}}return maxSum;}

演算法二：

這個只是對演算法一進行了一些最佳化：

這種演算法，時間複雜度O(N^2)

這裡i 表示的序列的開始位置，不斷推進開始位置，依次計算每個序列和，並把每輪求解的與最大值比較，把大於最大值的

當前值賦值給最大值。

public static int maxSum2(int[] a) {int maxSum = 0;for (int i = 0; i < a.length ; i++) {

int thisSum = 0;for (int j = i; j < a.length; j++) {

thisSum += a[j];

if (thisSum > maxSum) {maxSum = thisSum;}}}return maxSum;}

演算法三：

時間複雜度：O（N）

思想分析：

要求解序列中最大的和，那麼需要得到，每個序列的和，並比較值

int[] a = {-1, 0, 1, 2, -3, 8, 6};

因為 -1, 0, 1, 2, -3 的 和 <0 因此序列的開始位置可以從8 開始

/**

* 經典演算法：這個演算法只對資料進行一次掃描，一旦a[i] 被讀入並處理，就不需要被記憶，

* 因此，如果陣列在磁碟上或透過網際網路傳送，那麼它就可以按順序讀入，在主存中不必存

* 儲陣列的任何部分。

* 並且在任意時刻，演算法都能對它已經讀入的資料給出子序列問題的正確答案。（這種演算法叫作聯機演算法）

* @param a

* @return

*/

public static int maxSubSum4(int[] a) {int maxSum = 0,thisSum = 0;

for (int j = 0; j < a.length; j++) {thisSum += a[j];

if (thisSum > maxSum) {maxSum = thisSum;} else if (thisSum < 0) {thisSum = 0;}}return maxSum;}