最长连续子序列（dp,分而治之递归）

5227: 最大子列和问题

时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte
总提交: 76 测试通过:46

描述

给定KK个整数组成的序列{ N₁, N₂, ..., N_K }，“连续子列”被定义为{ N_i, N_i+1, ..., N_j }，其中1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：与样例等价，测试基本正确性；

数据2：10²个随机整数；

数据3：10³个随机整数；

数据4：10⁴个随机整数；

数据5：10⁵个随机整数；

输入

输入第1行给出正整数K (K≤100000)；第2行给出K个整数，其间以空格分隔。

输出

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

样例输入

6 -2 11 -4 13 -5 -2

样例输出

分而治之

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+5;
 4 int arr[N];
 5 int judge(int first,int ending){  //分成子问题来做
 6     if(first==ending){  //最终都会变成长度为1的子序列
 7         return arr[first];
 8     }
 9     int mid=(first+ending)/2;
10     int sum1=judge(first,mid);   //mid左边的最大值
11     int sum2=judge(mid+1,ending);  //mid右边的最大值
12     int lmax=arr[mid],rmax=arr[mid+1],sum=0;
13     for(int i=mid;i>=first;i--){
14         sum+=arr[i];
15         lmax=max(lmax,sum);
16     }
17     sum=0;
18     for(int i=mid+1;i<=ending;i++){
19         sum+=arr[i];
20         rmax=max(rmax,sum);
21     }
22     int ans=lmax+rmax;
23     if(ans<sum1)  ans=sum1;
24     if(ans<sum2)  ans=sum2;
25     return ans;
26 }
27 int main()
28 {
29     int n,num=0;
30     scanf("%d",&n);
31     for(int i=1;i<=n;i++){
32         scanf("%d",&arr[i]);
33         if(arr[i]<0) num++;
34     }
35     if(num==n) {printf("0
");return 0;}
36     int zhi=judge(1,n);
37     printf("%d
",zhi);
38     return 0;
39 }

View Code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+5;
 4 int main()
 5 {
 6     int n,dp[N],num=0;
 7     scanf("%d",&n);
 8     for(int i=1;i<=n;i++){
 9         scanf("%d",&dp[i]);
10         if(dp[i]<0) num++;
11     }
12     if(num==n) {printf("0
");return 0;}
13     int ans=dp[1];dp[0]=0;
14     for(int i=1;i<=n;i++){
15         if(dp[i-1]>0) dp[i]+=dp[i-1];//dp[i]==max(dp[i],dp[i-1]+num[i])
16         else dp[i]+=0;
17         ans=max(ans,dp[i]);
18     }
19     printf("%d
",ans);
20     return 0;
21 }
22 
23 
24 
25 
26 #include <bits/stdc++.h>
27 using namespace std;
28 const int N=1e5+5;   //求最长子序列 并且输出第一个元素和最后一个元素
29 int main()
30 {
31     int n,dp[N],num=0;
32     scanf("%d",&n);
33     for(int i=1;i<=n;i++){
34         scanf("%d",&dp[i]);
35         if(dp[i]<0) num++;
36     }
37     if(num==n) {printf("0
");return 0;}
38     int flag,u,v,sum=0,maxx=dp[1];
39     for(int i=1;i<=n;i++){   
40         if(sum<0){     //小于要舍弃
41             sum=dp[i];
42             u=i;
43         }
44         else sum+=dp[i];
45         if(sum>maxx){
46             maxx=sum;
47             flag=u;
48             v=i;
49         }
50 
51     }
52     printf("bian1:%d bian2:%d maxx=%d
",u,v,maxx);
53     return 0;
54 }

View Code