最近想學(xué)DP，鍛煉思維，記錄一下自己踩到的坑,來寫一波詳細(xì)的結(jié)題報(bào)告，持續(xù)更新。

題目鏈接：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 4 Case 2: 7 1 6

Author

Ignatius.L

Recommend

We have carefully selected several similar problems for you:??1069?2084?1058?1421?1024?

這一個(gè)題是一個(gè)基本題型，先分析數(shù)據(jù)這點(diǎn)很重要，剛剛踩坑，這里每個(gè)ai大于-1000，小于1000，那么min為-1e3*1e5，也就是說求和后最小值最大值為1e8量級，那么比較時(shí)最大最小值一定設(shè)置比這個(gè)量級大或在這個(gè)量級最大，而我沒考慮到如果全為負(fù)數(shù)時(shí)的情況。

開始說題目，這個(gè)題目找最大子串，對于任意一個(gè)元素，它有兩種可能性，做上個(gè)子串的最后一個(gè)字符，作以自己開頭的子串的第一個(gè)字符，我們這里不考慮當(dāng)前字符后續(xù)字符，因?yàn)镈P子問題無后效性，那么兩種狀態(tài)到了，我們要找出兩種狀態(tài)分支的條件，如果一個(gè)元素跟著前面的大哥混沒前途，那就不跟他混了，自立山頭，不前面序列的和都小于0，不如自己做開頭。即可寫出狀態(tài)轉(zhuǎn)移方程。,這里問什么沒寫等于0呢，因?yàn)轭}目的要求是找最靠前的左端點(diǎn)，所以這等于號要放到上面，但是我們怎么存儲(chǔ)端點(diǎn)呢？一樣的狀態(tài)轉(zhuǎn)移，我跟前面的老大哥們混，我的頭頭肯定是前面的老大哥，所以那我的老大哥也是這個(gè)子序列的第一個(gè)，如果這個(gè)小團(tuán)伙沒落了，我自立山頭，那么后來的人的大哥肯定會(huì)是我，所以就有了狀態(tài)轉(zhuǎn)移方程，再開一維，也可以再開一個(gè)數(shù)組，我不太建議跑好幾遍循環(huán)的方法，能簡化就簡化。

if(dp[i-1][1]<0||i==1) //i==1細(xì)節(jié)操作，自己想一下 {dp[i][0]=i;dp[i][1]=a[i]; } else {dp[i][0]=dp[i-1][0];dp[i][1]=dp[i-1][1]+a[i]; }

應(yīng)該沒什么要注意了，還有就是 初始化，這是多組輸入。

總結(jié)

以上是生活随笔為你收集整理的杭电60题--part 1 HDU1003 Max Sum（DP 动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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