[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[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;}

#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;}