最长连续子序列（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

样例输出

分而治之

 #include <bits/stdc++.h>

 using namespace std;

 const int N=1e5+;

 int arr[N];

 int judge(int first,int ending){  //分成子问题来做

     if(first==ending){  //最终都会变成长度为1的子序列

         return arr[first];

     }

     int mid=(first+ending)/;

     int sum1=judge(first,mid);   //mid左边的最大值

     int sum2=judge(mid+,ending);  //mid右边的最大值

     int lmax=arr[mid],rmax=arr[mid+],sum=;

     for(int i=mid;i>=first;i--){

         sum+=arr[i];

         lmax=max(lmax,sum);

     }

     sum=;

     for(int i=mid+;i<=ending;i++){

         sum+=arr[i];

         rmax=max(rmax,sum);

     }

     int ans=lmax+rmax;

     if(ans<sum1)  ans=sum1;

     if(ans<sum2)  ans=sum2;

     return ans;

 }

 int main()

 {

     int n,num=;

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d",&arr[i]);

         if(arr[i]<) num++;

     }

     if(num==n) {printf("0\n");return ;}

     int zhi=judge(,n);

     printf("%d\n",zhi);

     return ;

 }

 #include <bits/stdc++.h>

 using namespace std;

 const int N=1e5+;

 int main()

 {

     int n,dp[N],num=;

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d",&dp[i]);

         if(dp[i]<) num++;

     }

     if(num==n) {printf("0\n");return ;}

     int ans=dp[];dp[]=;

     for(int i=;i<=n;i++){

         if(dp[i-]>) dp[i]+=dp[i-];//dp[i]==max(dp[i],dp[i-1]+num[i])

         else dp[i]+=;

         ans=max(ans,dp[i]);

     }

     printf("%d\n",ans);

     return ;

 }

 #include <bits/stdc++.h>

 using namespace std;

 const int N=1e5+;   //求最长子序列 并且输出第一个元素和最后一个元素

 int main()

 {

     int n,dp[N],num=;

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d",&dp[i]);

         if(dp[i]<) num++;

     }

     if(num==n) {printf("0\n");return ;}

     int flag,u,v,sum=,maxx=dp[];

     for(int i=;i<=n;i++){

         if(sum<){     //小于要舍弃

             sum=dp[i];

             u=i;

         }

         else sum+=dp[i];

         if(sum>maxx){

             maxx=sum;

             flag=u;

             v=i;

         }

     }

     printf("bian1:%d bian2:%d maxx=%d\n",u,v,maxx);

     return ;

 }

巴特西

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

5227: 最大子列和问题

最新文章

热门文章