最大子序列和問(wèn)題

給定（可能有負(fù)的）整數(shù),A1、A2,...,AN,求∑k=ijAk的最大值。（為方便起見(jiàn)，如果所有整數(shù)均為負(fù)數(shù)，則最大子序列和為0）。 $$給定（可能有負(fù)的）整數(shù),A_1、A_2,...,A_N,求/sum_{k=i}^j A_k的最大值。（為方便起見(jiàn)，如果所有整數(shù)均為負(fù)數(shù)，則最大子序列和為0）。$$

第一種算法O(N^3)

第二種算法O(N^2)

第三種算法O(N logN),分治法 最大子序列的和可能在三處出現(xiàn)，或者出現(xiàn)在輸入數(shù)據(jù)的左半部，或者出現(xiàn)在輸入數(shù)據(jù)的右半部份，或者出現(xiàn)在輸入數(shù)據(jù)的中間部分。前兩種情況可以遞歸求解，第三種情況的最大和可以通過(guò)求出前半部分（包含前半部分最后一個(gè)元素）的最大和以及后半部分（包含后半部分第一個(gè)元素）的最大和而得到。此時(shí)將這兩個(gè)相加。

第四種算法O(N) 這種算法是比較難看出正確性的。可以知道，當(dāng)a[i]是負(fù)的時(shí)，那么它不可能作為最有序列的起點(diǎn)，因?yàn)槿魏伟琣[i]的作為起點(diǎn)的序列都可以通過(guò)用a[i+1]作為起點(diǎn)而得到改進(jìn)。類似地，任何負(fù)的子序列不可能是最優(yōu)子序列的前綴。如果在循環(huán)中檢測(cè)到從a[i]到a[j]的子序列是負(fù)的，那么可以推進(jìn)i。關(guān)鍵的結(jié)論是，我們不僅可以把i推進(jìn)到i+1, 而且實(shí)際上還可以把它一直推進(jìn)到j(luò)+1。為了看清楚這一點(diǎn)，令p為i+1到j(luò)之間的任一下標(biāo)。開(kāi)始于下標(biāo)p的任意子序列都不大于在下標(biāo)i開(kāi)始并包含從a[i]到a[p-1]的子序列的對(duì)應(yīng)的子序列，因?yàn)楹竺娴倪@個(gè)子序列不是負(fù)的（j是使得從下標(biāo)i開(kāi)始其值成為負(fù)值的序列的第一個(gè)下標(biāo)）。因此，把i推進(jìn)到j(luò)+1是沒(méi)有風(fēng)險(xiǎn)的。