方法一(具备c++语法基础即可):暴力穷举法,枚举左端点和右端点#define _CRT_SECURE_NO_WARNINGS 1#include<cstdio>#include<iostream>using namespace std;#define N 1e5//方法一,暴力穷举法,枚举左端点和右端点int solve(int* arr,int n){ int max_sum=arr[0]; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int sum = 0; for (int k = i; k <= j; k++) { sum += arr[k]; } if (sum > max_sum) { max_sum = sum; } } } return max_sum;}int main(){ //获取用户输入 int arr[(unsigned)N] = { 0 }; cout << "请输入列表的大小:"; cout << endl; int n; cin >> n; cout << "请输入列表的数据:"; for (int i = 0; i < n; i++) { cin >> arr[i]; } cout << endl; //求解最大连续子序列和 int max; max = solve(arr,n); cout << "最大连续子序列和是:" << max << endl; return 0;}
方法二(需了解前缀和):#include<iostream>#include<stdio.h>using namespace std;#define N 1e5int main(){ //下标 1 2 3 4 5 6 7 8 9 // arr -1 2 5 -5 3 7 -6 8 -5 // s -1 1 6 1 4 11 5 13 8 //当即将用户输入的序列 arr 转化为前缀和序列 s cout<<"请输入数组的大小:"; int n,s[(unsigned)N]={0}; cin>>n; for(int i=1;i<=n;i++) { cin>>s[i]; s[i]+=s[i-1]; //从下标1开始放入数据 } //下面先解决相对更简单的问题,循序渐进理解 // “一个长度为n的整数序列,从中找出一段长度不超过m的连续子序列 ” // max( s[i] - min(s[j],i-m<=j<=i-1) ) // int ans=s[1];// int m=3;// for(int i=1;i<=n;i++)// {// int mi=100000;// for(int j=i-m;j<i;j++)// {// if(j>=0) mi=min(mi,s[j]);// }// ans=max(ans,s[i]-mi);// }// cout<<"最大连续子序列和为:"<<ans<<endl; //把 m 换成 n 即最大子序列和问题 int ans=s[1]; for(int i=1;i<=n;i++) { int mi=100000; for(int j=i-n;j<i;j++) { if(j>=0) mi=min(mi,s[j]); } ans=max(ans,s[i]-mi); } cout<<"最大连续子序列和为:"<<ans<<endl;} 方法三(分治法):
将一个序列对半切(mid),那么这个最大连续子序列和要么在[l,mid],要么在[mid+1,r],要么跨越两边。
那么就要求出[l,mid]的最大连续子序列和, [mid+1,r]的连续子序列和, 跨越两边的连续子序列和
前两个问题是子问题,可以递归去解决。 所以只要解决第三个问题,然后返回三者中的最大者
第三个问题,我们可以从中间开始,分别向两边枚举。
枚举的时间复杂度是O(n),递归的深度是logn, 所以复杂度是O(nlogn)#include<iostream>#include<cmath>#define N 1e5using namespace std;int getMaxNum(int a,int b,int c){ if (a > b&&a > c){ return a; } if (b > a&&b > c){ return b; } return c;}int DivideSolve(int*arr,int left,int right){ if(left==right) return max(0,arr[left]); int mid=(left+right)/2; int left_max=DivideSolve(arr,left,mid); int right_max=DivideSolve(arr,mid+1,right); int MidSum1 = 0, MidSum2 = 0,tmp = 0; for(int i=mid;i>=left; --i) { tmp += arr[i]; if(tmp>MidSum1) { MidSum1 = tmp; } } tmp = 0; for(int i=mid+1;i<=right;++i) { tmp += arr[i]; if(tmp>MidSum2) MidSum2 = tmp; } return getMaxNum(left_max,right_max,MidSum1+MidSum2);}int main(){ int arr[(unsigned)N] = { 0 }; cout << "请输入列表的大小:"; cout << endl; int n; cin >> n; cout << "请输入列表的数据:"; for (int i = 0; i < n; i++) { cin >> arr[i]; } cout << endl; int max; max = DivideSolve(arr,0,n); cout << "最大连续子序列和是:" << max << endl;}
|