max sum 知道用动态规划。考虑到负数，前导为0.。可是编译错了。。望解
Online Judge Online Exercise Online Teaching Online Contests Exercise Author
F.A.Q
Hand In Hand
Online Acmers
Forum | Discuss
Statistical Charts
Problem Archive
Realtime Judge Status
Authors Ranklist
C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
STD Contests
VIP Contests
Virtual Contests
DIY | Web-DIY beta
Recent Contests
solo_lhx
Mail 0(0)
Control Panel
Sign Out
【Hot】关于PAT/ACM培训的报名通知~
Max Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 80721 Accepted Submission(s): 18541
Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
[code=C/C++][/code]#include<iostream>
using namespace std;
#define max_len 200000
int sum[max_len];
int main()
{ int t,n;
cin>>t;
for(int i=1;i<=t;i++)
{ cin>>n;
int max=0,start=1,end=1,sm=0;
for(int j=1;j<=n;j++)
cin>>sum[j];
int j=2,flag;
while(sum[j]<0) j++;
if((j==n+1)&&sum[1]<0) flag=1;
else if((j==n+1)&&sum[1]==0)flag=-1;
else flag=0;
switch(flag){
case 0:
for(int i=1;i<=n;i++)
{if(sm>=0) sm+=sum[i];
else{sm=sum[i];start=i;}
if(sm>max){max=sm;end=i;}
}
break;
case 1:
max=sum[1];
for(int i=2;i<=n;i++)
if(sum[i]>max) {max=sum[i];start=end=i;}
break;
case -1:
max=0; start=end=1;
break;
}
cout<< "Case "<<i<<":"<<endl;
cout<<max<<" "<<start<<" "<<end;
if(i!=t)
{cout<<"\n"<<endl;}
else cout<<endl;
}
return 0;
}
[解决办法]
这是经典问题，求最大字段和，动态规划算法在O(n)完成。
- C/C++ code
template<class T>T maxSubSum(T* arr,int len){ T *b=new T[len]; T max=b[0]=arr[0]; for(int i=1;i<len;i++) { b[i]=b[i-1]>0?b[i-1]+arr[i]:arr[i]; if(b[i]>max)max=b[i]; } return max;}