hdu1231最大连续子序列DP/两点法

最大连续子序列

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

 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速度略坑