最大连续子段和
最近在學(xué)習(xí)動態(tài)規(guī)劃，將自己的所思所想所得記錄下來，檢驗(yàn)自己是否真正懂了。
?
問題描述：
給定一個(gè)數(shù)組，記錄一串?dāng)?shù)字，可正可負(fù)，現(xiàn)要求出其中最大的連續(xù)子段和。
?
用數(shù)組A[N]記錄所要求的數(shù)組，用數(shù)組B[N]來記錄連續(xù)子段和的狀態(tài)
通過分析，可以知道：
當(dāng)B[K]>0時(shí)，無論B[K]為何值，B[K]=B[K-1]+A[K]
當(dāng)B[K]<0時(shí)，也就是B[K]記錄到一個(gè)A[J]是負(fù)的，可以把B[K]變成負(fù)的，那么B[J]記錄的這一段應(yīng)該截掉，應(yīng)為無論后面的A[K]多大，加上個(gè)負(fù)數(shù)總不可能是最大的子段和，因此將B[K]=A[K]，重新開始記錄。
?
故動態(tài)轉(zhuǎn)移方程便可得出
B[K] = MAX(B[K-1]+A[K] , A[K])
?
看個(gè)實(shí)例
k????? 1????? ?2????? ?3??????? 4
a[k] ?3?????-4???????2????????10
b[k]? 3?????-1?????? 2??????? 12
?
必須記住B[K]是狀態(tài)量，要獲得最大連續(xù)子段和，只需在數(shù)組B中掃描一遍得到最大的數(shù)即可。
?一個(gè)有N個(gè)整數(shù)元素的一維數(shù)組{A[0],A[1],....,A[N-1],A[N]},這個(gè)數(shù)組有很多連續(xù)的子數(shù)組，那么連續(xù)子數(shù)組之和的最大的一個(gè)的值是什么？
? ?先給出一個(gè)時(shí)間復(fù)雜度為O(N^2)的求解程序?qū)崿F(xiàn)，思想很簡單，就是遍歷數(shù)組中所有的子數(shù)組，代碼如下：
[java]?view plaincopy
因?yàn)樽訑?shù)組求和滿足動態(tài)規(guī)劃的后無效特性，所以可以使用動態(tài)規(guī)劃的思想，從分治的算法中得到提示：可以考慮數(shù)組的第一個(gè)元素A[0]，以及最大的一段數(shù)組(A[i],...A[j])跟A[0]之間的關(guān)系，有一下幾種情況：
1.當(dāng)0=i=j時(shí)，元素A[0]元素本身構(gòu)成和最大的一段；
2.當(dāng)0=i<j時(shí)，和最大的一段以A[0]開始；
3.當(dāng)0<i時(shí)，元素A[0]跟和最大的一段沒有關(guān)系。
從上面的三種情況可以將一個(gè)大問題(N個(gè)元素的數(shù)組)轉(zhuǎn)化為一個(gè)較小的問題(n-1個(gè)元素的數(shù)組)。假設(shè)知道(A[1],...,A[N-1])中包含A[1]的和最大的一段的和為start[1]。那么，根據(jù)上面分析的三種情況，不難看出(A[0],...,A[N-1])中問題的解all[0]是三種情況的最大值max{A[0],A[0]+start[1],all[1]}。通過問題分析，可以看到問題滿足無后效性，可以使用動態(tài)規(guī)劃的方法來解決。
程序代碼實(shí)現(xiàn)如下：
[java]?view plaincopy
總結(jié)
