评论

收藏

[C++] 【C++分治法/前缀和法/穷举法】最大连续子序列和问题

编程语言 编程语言 发布于:2021-12-11 22:46 | 阅读数:294 | 评论:0

方法一(具备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;}
DSC0000.png
方法二(需了解前缀和):
#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;}

关注下面的标签,发现更多相似文章