動(dòng)態(tài)規(guī)劃法求解最大連續(xù)子序列和問(wèn)題

張瑋

摘要

最大連續(xù)子序列和問(wèn)題是一個(gè)經(jīng)典問(wèn)題，有多種求解方法，每種方法的時(shí)間復(fù)雜度大不一樣，用動(dòng)態(tài)規(guī)劃法求解該問(wèn)題的時(shí)間復(fù)雜度為0（n），是所有方法中時(shí)間效率最優(yōu)的。本文詳細(xì)闡述了用動(dòng)態(tài)規(guī)劃法求解最大連續(xù)子序列和問(wèn)題的整個(gè)分析過(guò)程，介紹了動(dòng)態(tài)規(guī)劃法求解問(wèn)題的特點(diǎn)，最后給出了算法的實(shí)現(xiàn)代碼和解釋。

【關(guān)鍵詞】動(dòng)態(tài)規(guī)劃 最大連續(xù)子序列和

1 引言

動(dòng)態(tài)規(guī)劃法是解決最優(yōu)化問(wèn)題的一種常用方法，其基本方法是將欲求解的問(wèn)題劃分為規(guī)模更小的子問(wèn)題，原問(wèn)題的解蘊(yùn)含在子問(wèn)題的最優(yōu)解中。用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，通常情況下其子問(wèn)題會(huì)相互重疊，因此通常采用自底向上的迭代求解方法，并在計(jì)算過(guò)程中記錄下每一個(gè)子問(wèn)題的解，以便于重復(fù)使用。動(dòng)態(tài)規(guī)劃法是一種求解問(wèn)題的思想，沒(méi)有固定的公式，針對(duì)不同的問(wèn)題都有特定的算法。

最大連續(xù)子序列和問(wèn)題描述如下：給定一個(gè)序列A={a₁，a₂，a₃，….a_n}，求該序列的一個(gè)連續(xù)子序列{a_i，a_i+1，…，a_j-1，a_j}，其中1≤i≤j≤n，使得該子序列的和為最大。對(duì)于該問(wèn)題，求解算法有多種，最壞的方法是枚舉所有可能子序列，從中找出和為最大的序列，這種方法時(shí)間復(fù)雜度為O（n³）。用動(dòng)態(tài)規(guī)劃法求解該問(wèn)題的時(shí)間復(fù)雜度為O（n）。下面就如何用動(dòng)態(tài)規(guī)劃法的求解該問(wèn)題做詳細(xì)闡述。

2 問(wèn)題分析與算法推導(dǎo)

動(dòng)態(tài)規(guī)劃法的求解問(wèn)題的基本方法是將原問(wèn)題分為若干個(gè)階段，由前一階段的最優(yōu)解求出下一階段的最優(yōu)解。用動(dòng)態(tài)規(guī)劃法解決問(wèn)題，需要找出各階段之間的聯(lián)系，即由一個(gè)階段發(fā)展為另一個(gè)階段的狀態(tài)轉(zhuǎn)移方程。對(duì)原問(wèn)題階段的劃分應(yīng)滿足最優(yōu)性原理。最大連續(xù)子序列和問(wèn)題用動(dòng)態(tài)規(guī)劃法求解，關(guān)鍵在于子問(wèn)題（階段）的劃分和狀態(tài)轉(zhuǎn)移方程的建立。

假設(shè)有整數(shù)序列Qn={q₁，q₂，q₃，……q_n-1，q_n}，要求找出Q_n的最大連續(xù)子序列和。不妨假設(shè)Q_n的最大連續(xù)子序列和對(duì)應(yīng)的子序列為q_k，q_k+1，….，q_w，其中1≤k≤w≤n，顯然k和w的取值可能是1到n中的任何值，或者說(shuō)Q_n的最大連續(xù)子序列和必然是以某個(gè)q_w（1≤w≤n）元素結(jié)尾的連續(xù)子序列的和，不妨假設(shè)S_k（1≤k≤n）代表Q_n中以q_k為結(jié)尾的最大連續(xù)子序列和，則求Q_n最大連續(xù)子序列和問(wèn)題轉(zhuǎn)化為找最大的S_k的問(wèn)題。怎樣求s_k？按照動(dòng)態(tài)規(guī)劃法應(yīng)該找出從一個(gè)階段向下一個(gè)階段演進(jìn)的狀態(tài)轉(zhuǎn)移方程，既找出S_k-1和S_k的關(guān)系。顯然有S₁=q₁，S2和S1之間存在什么樣的關(guān)系呢？如果q₁+q₂=q₂，則S₂=S₁+q₂;若q₁+q₂≤q₂，那S₂=q₂，由此推導(dǎo)出：

①式中2≤k≤n。對(duì)①式可以用歸納法簡(jiǎn)單證明。

結(jié)合公式①對(duì)于Qn中以元素q_k（k≥1）為結(jié)尾的最大連續(xù)子序列和求解方程如下：

公式②即為求S_k的狀態(tài)轉(zhuǎn)移方程。Q_n的最大連續(xù)子序列和為max（S₁，S₂，S₃，……，S_n-1，S_n）。

3 算法實(shí)現(xiàn)

下面給出按照公式②設(shè)計(jì)的C語(yǔ)言源代碼。

[算法]求序列a的最大連續(xù)子序列和并輸出該子序列

void maxSubAxray（int a[]，int n）{//a為要求解的序列，n為序列長(zhǎng)度

int*s=（int*）malloc（n*sizeof（int））;//存儲(chǔ)以每個(gè)元素結(jié)尾的最大連續(xù)子序列和

int*start=（int*）malloc（n*sizeof（int））;//存儲(chǔ)每個(gè)最大連續(xù)子序列對(duì)應(yīng)的起始位置

int i，max=0;//max記錄最大連續(xù)子序列和的序列結(jié)尾元素的位置

for（i=0;i

//依次求出每個(gè)元素結(jié)尾的最大連續(xù)子序列和，及其對(duì)應(yīng)的起始元素位置for（i=1;i

if（s[i-1]+a[i]>a[i]）{s[i]=s[i-1]+a[i];start[i]=start[i-1]：}

}

for（i=0;i<10;i++）{//找出原問(wèn)題的最大連續(xù)子序列和對(duì)應(yīng)序列的結(jié)尾元素位置

if（s[max]

}

//輸出最大連續(xù)子序列和及其對(duì)應(yīng)的子序列

printf（"＼n最大連續(xù)子序列和是：%d＼n"，s[max]）;

printf（"對(duì)應(yīng)的連續(xù)子序列是："）;

for（i=start[max];i<=max;i++）printf（"%d"，a[i]）;

free（s）;

free（start）;

}

4 結(jié)語(yǔ)

動(dòng)態(tài)規(guī)劃法求解問(wèn)題的關(guān)鍵在于如何將原問(wèn)題合理地劃分為多個(gè)相似的子問(wèn)題以減小問(wèn)題的規(guī)模。就本文所論述的最大連續(xù)子序列和問(wèn)題而言，用動(dòng)態(tài)規(guī)劃法解決的關(guān)鍵就在于如何觀察到原問(wèn)題實(shí)際上是尋找以某個(gè)元素為結(jié)尾的一個(gè)連續(xù)子序列。通常情況下，在實(shí)際應(yīng)用中不同的問(wèn)題用動(dòng)態(tài)規(guī)劃法求解的具體算法是不同的，需要根據(jù)問(wèn)題的特點(diǎn)做細(xì)致的分析，合理劃分階段，建立正確的狀態(tài)轉(zhuǎn)移方程。

參考文獻(xiàn)

[1]（美）Thomas H.Cormen等著，殷建平等譯.算法導(dǎo)論（第3版）[M].機(jī)械工業(yè)出版社，2016.

[2]劉雄輝等.動(dòng)態(tài)規(guī)劃思想在ACM競(jìng)賽中的應(yīng)用研究[J].電腦知識(shí)與技術(shù)：學(xué)術(shù)交流，2017（6X）：238-239.