【C++分治法/前缀和法/穷举法】最大连续子序列和问题
方法一（具备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;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; } 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;}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 34 5 67 89 // arr -1 2 5 -5 3 7 -6 8 -5//s-1 1 6 1 4 11 5 13 8 //当即将用户输入的序列 arr 转化为前缀和序列 scout<<"请输入数组的大小：";int n,s[(unsigned)N]={0};cin>>n;for(int i=1;i<=n;i++){ cin>>s; s+=s; //从下标1开始放入数据 }//下面先解决相对更简单的问题，循序渐进理解// “一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列 ”// max( s-min(s,i-m<=j<=i-1)) //int ans=s;//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);// }// ans=max(ans,s-mi);//}//cout<<"最大连续子序列和为："<<ans<<endl;//把 m 换成 n 即最大子序列和问题int ans=s;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); } ans=max(ans,s-mi);}cout<<"最大连续子序列和为："<<ans<<endl;}方法三（分治法）：
将一个序列对半切（mid)，那么这个最大连续子序列和要么在，要么在，要么跨越两边。
那么就要求出的最大连续子序列和， 的连续子序列和，跨越两边的连续子序列和
前两个问题是子问题，可以递归去解决。 所以只要解决第三个问题，然后返回三者中的最大者
第三个问题，我们可以从中间开始，分别向两边枚举。
枚举的时间复杂度是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); 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; if(tmp>MidSum1) { MidSum1 = tmp; } } tmp = 0; for(int i=mid+1;i<=right;++i) { tmp += arr; 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; } cout << endl; int max; max = DivideSolve(arr,0,n); cout << "最大连续子序列和是：" << max << endl;}
https://blog.51cto.com/u_15397571/4787148
页:
[1]