題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1003

Problem Description Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input 2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5
Sample Output Case 1: 14 1 4Case 2: 7 1 6


思路一： 剛開始的第一反應(yīng)就是枚舉，枚舉一個(gè)開頭位置i，一個(gè)結(jié)尾位置j>=i，再求a[i..j]之間所有數(shù)的和，找出最大的就可以啦。當(dāng)然代價(jià)也是很高的O(N^3)。

如下代碼：

for(int i = 1; i <= n; i++){for(int j = i; j <= n; j++){int sum = 0;for(int k = i; k <= j; k++)sum += a[k]; max = Max(max, sum);} }

思路二： 我們發(fā)現(xiàn)a[i..j]的和不是a[i..j – 1]的和加上a[j]么？所以我們?cè)谶@里當(dāng)j增加1的時(shí)候把a(bǔ)[j]加到之前的結(jié)果上不就可以了么？對(duì)！所以我們毫不費(fèi)力地降低了復(fù)雜度，得到了一個(gè)新地時(shí)間復(fù)雜度為O(n^2)的更快的算法。
代碼如下：

for(int i = 1; i <= n; i++){int sum = 0;for(int j = i; j <= n; j++){sum += a[j];max = Max(max, sum);} }
思路三：

動(dòng)態(tài)規(guī)劃大顯身手。我們記錄dp[i]表示以a[i]結(jié)尾的全部子段中最大的和。我們看一下剛才想到的，我取不取a[i – 1],如果取a[i – 1]則一定是取以a[i – 1]結(jié)尾的子段和中最大的一個(gè)，所以是dp[i – 1]。 那如果不取dp[i – 1]呢？那么我就只取a[i]孤零零一個(gè)好了。注意dp[i]的定義要么一定取a[i]。 那么我要么取a[i – 1]要么不取a[i -1]。 那么那種情況對(duì)dp[i]有利？ 顯然取最大的嘛。所以我們有dp[i] = max(dp[i – 1]+ a[i], a[i]) 其實(shí)它和dp[i] = max(dp[i – 1] , 0) + a[i]是一樣的，意思是說之前能取到的最大和是正的我就要，否則我就不要！初值是什么？初值是dp[1] = a[1]，因?yàn)榍懊鏇]的選了。

這樣，我們的時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度也是O(n)——因?yàn)橐涗沝p這個(gè)數(shù)組。我們注意到dp[i] = max(dp[i － 1]， 0) ＋ a[i]，看它只和dp[i – 1]有關(guān)，我們?yōu)槭裁匆阉涗浵聛砟?#xff1f;為了求所有dp[i]的最大值？不，最大值我們也可以求一個(gè)比較一個(gè)嘛。

我們定義endmax表示以當(dāng)前元素結(jié)尾的最大子段和，當(dāng)加入a[i]時(shí)，我們有endmax’ = max(endmax, 0) + a[i]，然后再順便記錄一下最大值就好了。

老生常談的問題來了。我們?nèi)绾握业揭粋€(gè)這樣的子段？請(qǐng)看偽代碼endmax = max(endmax, 0) + a[i], 對(duì)于endmax它對(duì)應(yīng)的子段的結(jié)尾顯然是a[i]，我們?cè)趺粗肋@個(gè)子段的開頭呢？ 就看它有沒有被更新。也就是說如果endmax’= endmax + a[i]則對(duì)應(yīng)子段的開頭就是之前的子段的開頭。否則，顯然endmax開頭和結(jié)尾都是a[i]了。說到這里是不是已經(jīng)明了呢？那就看看具體的代碼吧。

代碼如下：

for(int i=1; i<=n; i++){ if(b>0)b+=a[i]; elseb=a[i]; if(b>sum)sum=b; //sum=max(b,sum);}

下面就此題貼出完整代碼：

#include<iostream> #define M 5000+5 #define LL long long #include<cstring> using namespace std; LL MaxSum(int n,int a[]){ LL sum=0; int b=0; for(int i=1; i<=n; i++){ if(b>0)b+=a[i]; elseb=a[i]; if(b>sum)sum=b; //sum=max(b,sum);} return sum; } int main(){ int n,a[M],m;LL maxsum; while(cin>>n){for(m=0; m<n; m++) cin>>a[m]; int b[M]; for(m=0; m<n; m++) b[m+1]=a[m]; maxsum=MaxSum(n,b); cout<<maxsum<<endl; }return 0; }

總結(jié)

以上是生活随笔為你收集整理的HD 1003 Max Sum (最大字段和问题)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。