Maximum sum
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 44476   Accepted: 13796

Description

Given a set of n integers: A={a1, a2,…, an}, we define a function d(A) as below:

Your task is to calculate d(A).

Input

The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input. 
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, …, an. (|ai| <= 10000).There is an empty line after each case.

Output

Print exactly one line for each test case. The line should contain the integer d(A).

Sample Input

1

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

Sample Output

13

简单的dp题。
首先是dp，就是把大的问题细化为可以立即解决的小问题。

这有点像数列：先确定n=1的情况，再确定n和n-1的关系，即可得出数列的通项公式。

提一句，楼主高考的时候，数列是最后一个大题，坐标浙江= =。

比如该题的寻找最大子序列，当n为1的时候很容易判定，取这唯一的一个值就好了，然后考虑n和n-1的关系。
我们用a[n]来记录每个值，用dp[n]来记录过程。
如果我们想由n-1的情况推出n的情况，我们是不是要知道n-1时前面的最大子序列和？ 而且，这个 和 是需要包含a[n-1]这个值的，否则a[n]无法和前面的序列相连。

思考之后我们可以的出，如果前面包含a[n-1]的最大子序列和，即dp[n-1],大于零，则我们可以得出：dp[n]=dp[n-1]+a[n] ,否则，dp[n]=a[n], 大于零就加上，有点贪心的感jio。
也因此，dp[]中是存在负数的，因为我们要保证 dp[n-1] 至少要包含 a[n-1]，否则无法相连，而且最大子序列 长度不能为0.

但此时dp[] 是最终答案了吗？
明显不是，因为 “最大子序列” 不要求每个dp[n-1]中包含a[n-1]。
但也已经接近尾声了。
我们可以知道，不管“最大子序列”在哪里结束，反正在 dp[n]前面的n-1 项中肯定存在，所以要求到dp[n]的最长子序列，只需从头到尾遍历更新一遍:

for(int i=1;i<n;i++)
　　if( dp[i-1] > dp[i] )
　　　　dp[i]=dp[i-1]

用l（左）数组和r（右）数组记录。

好了，这样子左右分别来一遍后，我们分别得到了 l[]和r[] 两个数组，其中 l[t] 代表 【1，t】（闭区间）内的最大子序列和，r[t]则代表【t，n】的。

而对于这题我们只需从1到n遍历一遍间断点相加 r[] 和 l[] 的值即可得到最大值。
for(int i=1;i<n;i++)
{
　　ans= max ( ans , l[i-1]+r[i])
}
得出答案answer。
有几个注意点：
1 一个测试点n是最大值50000，所以需要开大一点的数组，我因为这个找了半天错= =。
2 间断点本身只能取一次，被左或右取均可。
3 代码可以自己尝试一下，不贴了就。

希望看到的提个意见，评个论。
然后贴一个网站，poj提目推荐
https://www.cnblogs.com/rainydays/p/3671118.html

类似题目，poj2593
版权声明：本文为zgncbsylm原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/zgncbsylm/p/10569290.html