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—