最长子序列dp poj2479 题解

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:

$d(A)=\max_{1\leq s_1\leq t_1<s_2\leq t_2\leq n}\left\{\sum_{i=s_1}^{t_1}a_i+\sum_{j=s_2}^{t_2}a_j\right\}$

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 间断点本身只能取一次，被左或右取均可。

贴一个网址，poj题目推荐
https://www.cnblogs.com/rainydays/p/3671118.html

类似题目，poj2593

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=50009;
const int minn=-50000;

int main()
{
   // freopen("input.txt","r",stdin);
    int T,n,ans;
    int a[maxn],ls[2][maxn],rs[2][maxn];
    cin>>T;
    while(T--)
    {
          ans=minn;
          cin>>n;
          ls[0][0]=ls[1][0]=minn;rs[0][n+1]=rs[1][n+1]=minn;
          for(int i=1;i<=n;i++)
          {
                scanf("%d",&a[i]);
                ls[0][i]=max(ls[0][i-1]+a[i],a[i]);
                ls[1][i]=max(ls[0][i],ls[1][i-1]);
          }
          for(int i=n;i>=1;i--)
          {
                rs[0][i]=max(rs[0][i+1]+a[i],a[i]);
                rs[1][i]=max(rs[0][i],rs[1][i+1]);
          }

          for(int i=2;i<=n;i++)
          {
                ans=max(ans,ls[1][i-1]+rs[1][i]);
          }
          cout<<ans<<endl;
    }
}