HDU 1003 Max Sum【動态規劃求最大子序列和詳解 】Max Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 250714    Accepted Submission(s): 59365

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

Sample Output

Author

Ignatius.L

初來乍到，動态規劃也是剛剛接觸。剛開始用暴力法，Time limit……

在網上搜了代碼。大多是隻說是動态規劃經典問題、求最大子序列和，然後就是一串代碼。最好的就是帶了幾行注釋…沒有太多通俗的解釋…硬着頭皮看了一晚上，終于算是有了眉目想通了。

在這裡寫下自己對這個動态規劃求最大子序列和的了解，通俗一點的解釋。（隻是個人的了解哦，僅供參考）

這裡的求最大子序列和應該是變種了吧，呵呵，還要加上最大子序列的起始和終止位置……隻要知道怎麼求最大子序列和，那麼附加個位置應該不難的。

先來看代碼：

本想用通俗的話語來解釋這個道理，結果發現，通俗了以後就非文字所能描述的好的了，需要各種的手勢+紙筆畫一陣子，無奈表達能力有限，隻好……隻好用這樣的看似非常嚴密的數學推理來說明了（囧)

對于整個序列a[n]來說，它的所有子序列有很多很多，但是可以将它們歸類。

注意，是以**結尾的子序列，其中肯定是要包含**的了

以a[0]結尾的子序列隻有a[0]

以a[1]結尾的子序列有 a[0]a[1]和a[1]

以a[2]結尾的子序列有 a[0]a[1]a[2] / a[1]a[2] / a[2]

……

以a[i]結尾的子序列有a[0]a[1]……a[i-2]a[i-1]a[i]  / a[1]a[2]……a[i-2]a[i-1]a[i] /  a[2]a[3]……a[i-2]a[i-1]a[i] / …… /  a[i-1]a[i] / a[i]

所有以a[0] ~a[n]結尾的子序列分組構成了整個序列的所有子序列。

這樣，我們隻需求以a[0]~a[n]結尾的這些分組的子序列中的每一分組的最大子序列和。然後從n個分組最大子序列和中選出整個序列的最大子序列和。

觀察可以發現，0，1，2，……，n結尾的分組中，

maxsum a[0] = a[0]

maxsum a[1] = max( a[0] + a[1] ，a[1])  = max( maxsum a[0] + a[1] ，a[1]) 

maxsum a[2] = max( max ( a[0] + a[1] + a[2]，a[1] + a[2] )，a[2])  

= max(  max( a[0] + a[1] ，a[1]) + a[2] ， a[2]) 

= max(  maxsum a[1] + a[2] ， a[2])

依此類推，可以得出通用的式子。

maxsum a[i] = max（ maxsum a[i-1] + a[i]，a[i])

用遞歸……當然，不遞歸也應該是可以解決的。

我們從maxsum  a[0]開始算起。

以後的每個就是  maxsum a[i-1] + a[i] 和 a[i] 中取大的那個。

程式中判斷 前一個的最大子序列和小于零時，将其置為0，然後再加a[i] ，這樣不就是和a[i] 一樣大的麼；前一個的最大子序列和隻要大于零，那麼再加上a[i] 肯定比 a[i] 要大，這樣，帶有歸零的這個 maxsum a[i-1] + a[i] 就是以表示目前位置結束的子序列的最大和了。

剩下的就是要判斷起始和終點位置了。

在循環的過程中，每循環一次就算出一個以目前位置結束的最大子序列和。每次循環中最大的那個儲存下來，不就是最終所有最大子序列和中的最大值了麼。

其中temp儲存的是前一個位置的最大子序列和的開始位置（題目中是從1開始的哦）；當 sum > maxsum 時（程式中的條件，與說明時的maxsum不太一樣哦）就記錄最大值，并保持它的開始位置為temp，終止位置即為目前位置（i +1是因為題目中第一個為1，而不是0）；

當最大子序列和小于0時，将 temp = i + 2； 其中 i + 1 表示目前位置（理由如上），i + 2就表示目前位置的下一個位置了。既此最大子序列和為負值，那麼下一個的最大子序列和應該是它本身，而不再累加前邊的。

程式中就兩個if 語句，想要說明白還真不容易。

還有，有人會問，當整個序列全是負數時，還對嗎？負數也是成立的，如果全是負數的時候，它就是每次都隻取目前值作為最大值了，因為負的跟負的不就越加越小了嗎。

因為題目中給出的範圍是-1000 ～1000，是以這裡初始的maxsum 初始化為-1001 ，隻有比所有可能的值都小時才行。maxsum初始化為0；那麼當序列全是負數時，得出的最大值将是0……這就wrong了

 總之，隻要上一個子序列最大和為正，那麼無論目前值的正負，都會與目前的相加，這樣以目前值結尾的子序列最大和就會增大。（一個正數 加一個 正數2 或者負數 那麼都會比這個正數2 或負數原來要增大，同理，一個負數加任何一個數，都會使這個數減小，是以目前一子序列最大和小于零時，我們就歸零它了，相當于是不加任何數，而保留目前位置值本身）

記憶體優化版：

了解了以上思想後，觀察上一個代碼我們發現，那個a[10000]基本上就沒用啊，儲存了一些輸入資料，可是那些資料隻用了一次就沒用了。輸入資料的for循環和處理資料的for循環是一模一樣的，而且處理資料也隻是用到目前輸入的資料。

于是，數組也可以省去了，直接将兩個循環合并。輸入一個資料，直接累加……省下不少空間哦。