陳堅(jiān)強(qiáng)

摘要：隨著經(jīng)濟(jì)的發(fā)展、社會(huì)的進(jìn)步和科學(xué)研究的深入，要求用計(jì)算機(jī)解決的問題越來越復(fù)雜，規(guī)模越來越大。對(duì)求解這類問題的算法進(jìn)行分析具有特別重要的意義，下面通過分別使用分治法和動(dòng)態(tài)規(guī)劃法來求解最大子段和問題，并分析算法的優(yōu)劣。

關(guān)鍵詞：最大子段和；分治法；動(dòng)態(tài)規(guī)劃法；時(shí)間復(fù)雜度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）27-0163-01

1 最大子段和

給定由n個(gè)整數(shù)（可能為負(fù)整數(shù)）組成的序列a1，a2，a3…，an，求該序列形如∑ak（k=i，i+1…j）的子段和最大值。當(dāng)所有的整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為0。依次定義，所求的最優(yōu)值為

2 分治法求解最大子段和問題

針對(duì)最大子段和這個(gè)具體問題本身的結(jié)構(gòu)，從問題的本身的解的結(jié)構(gòu)可以看出，它適合于用分治法求解。如果將所給的序列a[1：n]分為長(zhǎng)度相等的兩段a[1：n/2]和a[n/2+1：n]，分別求出這兩段的最大子段和，則a[1：n]的最大子段和有三種情況：

（1）a[1：n]的最大子段和與a[1：n/2]的最大子段和相同；

（2）a[1：n]的最大子段和與a[n/2+1：n]的最大子段和相同；

（3）a[1：n]的最大子段和的起始位置在前半段，終止位置在后半段。

對(duì)于（1），（2）情況，我們可以按遞歸方法求得。對(duì)于情況（3）容易看出a[n/2]與a[n/2+1]在最優(yōu)子序列中。因此，我們可以在a[1：n/2]中計(jì)算出s1=max∑a[k]（k=i，i+1，…n/2）其中1<=i<=n/2，并在a[n/2+1：n]中算得s2=max∑a[k]（k=n/2+1…i）（n/2+1<=i<=n），則s1+s2即為（3）最優(yōu)值。

4 結(jié)論

由上面的分析可知，分治算法時(shí)間復(fù)雜度為O（nlogn），而動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為O（n）?？梢妱?dòng)態(tài)規(guī)劃算法其效率較高，算法較優(yōu)。相同點(diǎn)：分治法和動(dòng)態(tài)規(guī)劃法都需要問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。不同點(diǎn)：分治法的問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。而動(dòng)態(tài)規(guī)劃法的問題所分解出的各個(gè)子問題具有重疊性質(zhì)，即子問題之間有包含公共的子問題。

參考文獻(xiàn)：

[1] 周波，劉文強(qiáng)，喬付，等.算法設(shè)計(jì)與分析課程中最大子段和問題的教學(xué)探討[J].中國(guó)教育技術(shù)裝備，2013（27）.

[2] 袁佳樂. 淺析求解最大子段和問題的算法[J].西安文理學(xué)院學(xué)報(bào)，2009（3）.

[3] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].電子工業(yè)出版社，2001.

[4] 王能超.數(shù)值分析簡(jiǎn)明教程[M].高等教育出版社，2003.

[5] 廖慧芬，邵小兵. 動(dòng)態(tài)規(guī)劃算法的原理及應(yīng)用[J]. 中國(guó)科技信息，2005（21）.

[6] 廖作斌. 一種改進(jìn)的最大m子段和算法設(shè)計(jì)[J]. 湖北科技學(xué)院學(xué)報(bào)，2014（03）.

[7] 廖作斌. 高校計(jì)算機(jī)專業(yè)高級(jí)語言程序設(shè)計(jì)課程的教學(xué)改革[J].宜春學(xué)院學(xué)報(bào)，2010（4）.

[8] 王榮海，曾玉珠，廖作斌.基于集中形式的軟件工程課程設(shè)計(jì)[J].計(jì)算機(jī)教育，2010（17）.

[9] 廖慧芬，邵小兵. 動(dòng)態(tài)規(guī)劃算法的原理及應(yīng)用[J].中國(guó)科技信息，2005（21）.