TAG 动态规划
设maxd[n]为前n个数的最大子序列和
maxd[n]=max{ maxd[n-1], sum[n]-minX } 其中,minX=min{sum[i] | 1<=i<n}
同理,设rmaxd[n]为从n到序列完的最大子序列和
则答案为max{ maxd[i]+rmaxd[i+1] },时间复杂度为O(n)
#include <stdio.h>
const int N=50000;
int ans;
int t,n;
int a[N];
int sum[N],rsum[N];
int maxd[N],rmaxd[N];
int minp;
int max(int a, int b)
{
return a>b? a: b;
}
int min(int a,int b)
{
return a<b? a: b;
}
int main(int argc, char *argv[])
{
scanf("%d", &......
阅读全文