描述
给定KK个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：与样例等价，测试基本正确性；
数据2：102个随机整数；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；
输入
输入第1行给出正整数K (K≤100000)；第2行给出K个整数，其间以空格分隔。
输出
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。
样例输入
样例输出
分而治之
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\n");return 0;} 36 int zhi=judge(1,n); 37 printf("%d\n",zhi); 38 return 0; 39 }
dp
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\n");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\n",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\n");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\n",u,v,maxx); 53 return 0; 54 }
原文：https://www.cnblogs.com/qq-1585047819/p/10738503.html
