Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 15168 Accepted Submission(s): 6624
Problem Description 给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个， 例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和 为20。 在今年的数据结构考卷中，要求编写程序得到最大和，现在增加一个要求，即还需要输出该 子序列的第一个和最后一个元素。 Input 测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( < 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。 Output 对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元 素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。 Sample Input 6 -2 11 -4 13 -5 -2 10 -10 1 2 3 4 -5 -23 3 7 -21 6 5 -8 3 2 5 0 1 10 3 -1 -5 -2 3 -1 0 -2 0 Sample Output 20 11 13 10 1 4 10 3 5 10 10 10 0 -1 -2 0 0 0 Hint Hint Huge input, scanf is recommended. Source 浙大计算机研究生复试上机考试-2005年 Recommend JGShining DP 1 //状态方程为c[n] = max(c[n-1]+a[n], a[n]) 2 //c[0] = a[0] 3 4 //c[n]表示前n个元素的和 5 #include <iostream> 6 #include <stdio.h> 7 #define MAX 10005 8 using namespace std; 9 10 int main() 11 { 12 //freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); 13 int a[MAX]; 14 int c[MAX]; 15 int hold_start[MAX]; //保存起始点 16 int n; 17 while(cin >> n && n) 18 { 19 for(int i = 0; i < n; i++) 20 scanf("%d", &a[i]); 21 c[0] = a[0]; 22 hold_start[0] = a[0]; 23 for(int i = 1; i < n; i++) 24 { 25 if(c[i-1]>0) 26 { 27 c[i] = c[i-1]+a[i];//只要后面的和大于0，再加一个数就会比a[i]更大,把所有可能最大的连续段都加起来保存 28 hold_start[i] = hold_start[i-1];//最后找最大的那段 29 } 30 else 31 { 32 c[i] = a[i];//重新确定起点 33 hold_start[i] = a[i]; 34 } 35 } 36 int _max = c[0]; 37 for(int i = 1; i < n; i++) 38 _max = max(_max, c[i]); 39 if(_max < 0) 40 cout << "0 " << a[0] << " " << a[n-1] << endl; 41 else 42 { 43 for(int i = 0; i < n; i++) 44 if(c[i] == _max) 45 { 46 cout << _max << " " << hold_start[i] << " " << a[i] << endl; 47 break; 48 } 49 } 50 } 51 return 0; 52 } View Code
两点
1 #include<iostream> 2 #include<vector> 3 #define MAX -999999999 4 using namespace std; 5 6 int main(void) 7 { 8 int n; 9 while(cin>>n,n) 10 { 11 vector<int>arr(n,0); 12 int start=0,end=0,i,ok=0; 13 int sum=0,maxn=MAX,k=0; 14 for(i=0; i<n; i++) 15 { 16 cin>>arr[i]; 17 if(arr[i]>=0)ok=1; 18 } 19 if(ok) 20 { 21 for(i=0; i<n; i++) 22 { 23 sum+=arr[i]; 24 if(sum>maxn) 25 { 26 maxn=sum; 27 start=arr[k]; 28 end=arr[i]; 29 } 30 if(sum<0) 31 { 32 sum=0; 33 k=i+1; 34 } 35 } 36 cout<<maxn<<" "<<start<<" "<<end<<endl; 37 } 38 else 39 { 40 cout<<0<<" "<<arr[0]<<" "<<arr[n-1]<<endl; 41 } 42 } 43 return 0; 44 } View Code用G++超时，C++A，G++ IO速度略坑
转载于:https://www.cnblogs.com/Skyxj/p/3200054.html
