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 -5Sample Output
13 立即现场赛了。。3个人尽然没有会dp的sad。。
我仅仅有临阵磨枪了。
题意：给一个数列，求数列中不相交的两个子段和。要求和最大。 线性dp：线性dp的子状态与父状态一般相差一个元素，所以子问题通过加入一个增量而到达父状态。从最小的子问题到原问题。一层一层的状态转移呈现出线性递增的关系。所以称为线性dp。 题解:对于对于每一个状态i。求出[0,i-1]的最大子段和以及[i,n-1]的最大子段和 相加求最大的就可以。[0,i-1]从左往右扫描，[i，n-1]从右往左扫描。 #include <algorithm> #include <cstdio> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 50010; #define LL long long int a[maxn],left[maxn],right[maxn]; int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); left[0]=a[0]; for(int i=1;i<n;i++) left[i]=left[i-1]<0?a[i]:left[i-1]+a[i]; for(int i=1;i<n;i++) left[i]=max(left[i-1],left[i]); right[n-1]=a[n-1]; for(int i=n-2;i>=0;i--) right[i]=right[i+1]<0?a[i]:right[i+1]+a[i]; for(int i=n-2;i>=0;i--) right[i]=max(right[i+1],right[i]); int ans=-INF; for(int i=1;i<n;i++) ans=max(ans,left[i-1]+right[i]); printf("%d\n",ans); } return 0; }转载于:https://www.cnblogs.com/bhlsheji/p/5303498.html
