問題#
方案一#
思路##
先搜尋出所有的子序列，然后求和比較
代碼##
public static void maxSubSum1(int[] a) {
int maxSum = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++) {
int tempSum = 0;
for (int k = i; k <= j; k++) {
tempSum += a[k];
}
if (maxSum < tempSum) {
maxSum = tempSum;
startIndex = i;
endIndex = j;
}
}
}
System.out.println("this subsequence is from " + startIndex + " to " + endIndex + ", max sum is " + maxSum);
}
結(jié)果##
分析##
此方案用了三層循環(huán)，第一層循環(huán)確定子序列的起始位子（i），第二層循環(huán)確定子序列的終止位子（j）。通過第一層循環(huán)和第二層循環(huán)確定所有的子序列，然后再通過第三層循環(huán)求和。最后比較子序列的和，確定起始位子和終止位子。
此方案的時(shí)間復(fù)雜度為O(N^3 )，這完全取決于第三層for循環(huán)。所以為了提高效率，我們可以撤除第三層for循環(huán)（當(dāng)然不是所有的三層循環(huán)都能這么做）。
方案二#
思路##查詢
搜索出所有的子序列，然后求和比較。（相對(duì)于方案一，去除了第三層求和的for循環(huán)）
代碼##
public static void maxSubSum2(int[] a) {
int maxSum = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < a.length; i++) {
int tempSum = 0;
for (int j = i; j < a.length; j++) {
tempSum += a[j];
if (maxSum < tempSum) {
maxSum = tempSum;
startIndex = i;
endIndex = j;
}
}
}
System.out.println("this subsequence is from " + startIndex + " to " + endIndex + ", max sum is " + maxSum);
}
分析##
此方案用了三層循環(huán)，第一層循環(huán)確定子序列的起始位子，第二層循環(huán)確定子序列的終止位子。通過第一層循環(huán)和第二層循環(huán)確定所有的子序列，然后通過第二層for循環(huán)求和。時(shí)間復(fù)雜度為O(N^2)。
方案三#
思路##
方案一和方案二的第一層循環(huán)用來(lái)確定子序列的起始位子，第二層循環(huán)用來(lái)確定子序列的結(jié)束位子。從兩層循環(huán)的起始位子看，都是從0開始，但是對(duì)于最大子序列，其起始位子的值不可能為負(fù)數(shù)；進(jìn)一步看，如果最大子序列是AiAj，對(duì)于任意i<p<j，最大子序列的子序列AiAp的和一定大于0，所以對(duì)于任意從起始位子開始的子序列，若其和為負(fù)數(shù)，則丟棄，i繼續(xù)向前推進(jìn)，直到數(shù)列遍歷完畢。
代碼##
public static void maxSubSum3(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;
}
}
System.out.println(maxSum);
}
分析##
此方法對(duì)于i（子序列的其實(shí)位子）進(jìn)行了優(yōu)化，因?yàn)槲覀冴P(guān)注的只是最大子序列，所以不必搜尋出所有的子序列（和方案一、方案二的區(qū)別），只需找到所有Ai~Ap（i<p<j）的和不為負(fù)數(shù)的子序列，然而這種方式只需要一層循環(huán)即可，所以去掉了最外層的循環(huán)。然后求出這些子序列的和，然后比較。此算法的時(shí)間復(fù)雜度為O(N)。
該算法的一個(gè)附加優(yōu)點(diǎn)是，它對(duì)數(shù)據(jù)只進(jìn)行一次掃描，一旦a[i]被讀入處理，就不需要被記憶。因此，如果數(shù)組在磁盤上或通過互聯(lián)網(wǎng)傳播，那么它就可以被按順序讀入，在內(nèi)存中就不必存儲(chǔ)數(shù)組的任何部分。不僅如此，在任意時(shí)刻，算法都能對(duì)它已經(jīng)讀入的數(shù)據(jù)給出子序列問題的正確答案。具有這種 特性的算法叫做聯(lián)機(jī)算法（on-line algrithm）。僅需要常量空間并以線性時(shí)間運(yùn)行的聯(lián)機(jī)算法幾乎是完美的。
