poj 2479 最大連續子段和 dp算法

晚上一水~~poj2479，一道簡單的dp問題，回顧一下動态規劃

這道題是求一個序列中的兩個子段的最大和，是求純的最大和的一個變體，例如題目中給出的例子

1 -1 2 2 3 -3 4 -4 5 -5

in the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.

答案是 13

如何求一個序列的子段和：

分析：

思路很清晰的寫法，每次都判斷，目前dp值（即子串目前最大值），如例子中的： 1 0 2 4 7 4 8 4 9 4

這樣就很清楚了~~

先上ac代碼：

但是這題用暴力的 maxsub(map,i)+maxsub(map+i,n-i) 去做，是沒有用的，會tle，後來我将cin換成scanf，也是不行的，再後來用了這個方法：

究其原因是，用 maxsub(map,i)+maxsub(map+i,n-i) 純暴力方法，是 o(n^2) 的複雜度，後來改成 findmax(0,i) + findmax(i+1,n)-dp[i-1] 其實依然是 o(n^2) 的複雜度。。

ac代碼是用從左往右，找出正常的最大子串，然後用

求出從左往右，目前點的最大值，如果用例子中的值就是： 1 1 2 4 7 7 8 8 9 9

保證從左往右，一定是變大，找到一個點就可以找到這個點左邊的最大值~~

同理，可以計算從右往左的，一個點右邊的最大值，這樣就用空間換時間了，但是即使這樣，也隻跑出了438ms。。。

而且将scanf換成cout，又tle了

—end—