第2章 Android应用的界面编程
Maximum sum
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 Hint
In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.
Huge input,scanf is recommended. Source
POJ Contest,Author:Mathematica@ZSU
|
题意:
给你n个数字的序列。叫你找出两个连续子段。两子段不重合。使得两字段中所有数字的和最大。
思路:
开始因为没注意到不重合WA了数次!解法还是蛮简单的。从前往后和从后往前分别做一次最大子段和。然后枚举分段点。就可以得到答案了。
详细见代码:
#include<algorithm> #include<iostream> #include<string.h> #include<sstream> #include<stdio.h> #include<math.h> #include<vector> #include<string> #include<queue> #include<set> #include<map> //#pragma comment(linker,"/STACK:1024000000,1024000000") using namespace std; const int INF=0x3f3f3f3f; const double eps=1e-8; const double PI=acos(-1.0); const int maxn=50100; int dpl[maxn],dpr[maxn],ml[maxn],arr[maxn]; int main() { int t,n,i,ans; scanf("%d",&t); while(t--) { scanf("%d",&n); ans=-INF; dpl[0]=dpr[n+1]=ml[0]=0; for(i=1;i<=n;i++) { scanf("%d",&arr[i]); dpl[i]=max(arr[i],arr[i]+dpl[i-1]);//从前往后 ans=max(ans,dpl[i]); ml[i]=ans;//记录到i时的最大字段和 } ans=-INF;//必须要再次初始化。开始偷懒认为死一样的。结果会导致最后只有一个字段。数据见下 for(i=n;i>1;i--) { dpr[i]=max(arr[i],arr[i]+dpr[i+1]); ans=max(ans,ml[i-1]+dpr[i]); } printf("%d\n",ans); } return 0; } /* 1 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 */
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。