求最大子段和C语言_最大子段和问题的算法完整程序

㈠最大子段和

我直接在这个框里打，需要你再调试一下。。。

#include "stdio.h"

const long maxn=1000;

long a[maxn],opt[maxn+1];
long ans=0;

int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
opt[0]=0;
for(i=0;i<n;i++)
{
opt[i+1]=a[i];
if(opt[i]+a[i]>opt[i+1])
opt[i+1]=opt[i]+a[i];
if(opt[i+1]>ans) ans=opt[i+1];
}
printf("%d\n",ans);
return 0;
}

算法是这样的：

已知包含第n个数的最大子段
那么包含第n+1个数的最大子段有两种情况，一是包含“包含第n个数的最大子段”，要么就是不包含。比较一下哪个大就行。

最后的输出是对每个数计算包含这个数的最大子段，找出最大就行

㈡给定一个整数序列，怎么求出子段序列的最大和

具体代码如下：
#include<stdio.h>
int main(){
int max,sum,n,x;
while(scanf("%d",&n)!=EOF){
sum=0;
max=0;
while(n--){
scanf("%d",&x);
sum+=x;
if(sum>0){//sum大于0
if(sum>max){//sum大于max则sum赋值给max，否则继续加下一个数
max=sum;
}
}
else{//sum<0,置sum为0
sum=0;
}
}
printf("%d ",max);
}
return 0;
}

㈢ C语言最大双子段

这题可以用DP解
给定n个数求这n个数划分成互不相交的m段的最大m子段和。
经典的动态规划优化的问题。设f(i, j)表示前i个数划分成j段，且包括第i个数的最大m子段和，那么有dp方程：
f(i, j) = max { f(i - 1, j) + v[i], max {f(k, j - 1) + v[i]}(k = j - 1 ... i - 1) }
也就是说第i个数要么自己划到第j段，要么和前一个数一起划到第j段里面，转移是O(n)的，总复杂度O(n * n * m)。
可以引入一个辅助数组来优化转移。设g(i, j)表示前i个数划分成j段的最大子段和（注意第i个数未必在j段里面），那么递推关系如下：
g(i, j) = max{g(i - 1, j), f(i, j)}，分是否加入第i个数来转移
这样f的递推关系就变成：
f(i, j) = max{f(i - 1, j), g(i - 1, j - 1)} + v[i]，转移变成了O(1)
这样最后的结果就是g[n][m]，通过引入辅助数组巧妙的优化了转移。实现的时候可以用一维数组，速度很快。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000010,INF=0x3fffffff;
int f[N],g[N],a[N];
int max_sum(int m,int n)
{
int i,j,t;
for(i=1;i<=n;i++)
{
t=min(i,m);
for(j=1;j<=t;j++)
{
f[j]=max(f[j],g[j-1])+a[i];
g[j-1]>?=f[j-1];
}
g[j-1]>?=f[j-1];
}
return g[m];
}

int main()
{
int m=2,n;
while(scanf("%d",&n)==1)
{
for(int i=1;i<=n;i++)
{
f[i]=g[i]=-INF;
scanf("%d",&a[i]);
}
printf("%d\n",max_sum(m,n));
}
return 0;
}

㈣题目：最大子段求和问题。

#include <iostream.h>

void main()
{
int nmb[]={1,4,-15,4,9,23,-2,3,-21,1}; //任意数组

int nlength=sizeof(nmb)/sizeof(int);//数组长
int tempSum=nmb[0], maxvalue=0,beginCout,endCout;
for (int i=0;i<nlength;i++)//遍历字段，累加正数段
{
if (tempSum>0)//如果临时和大于0的
{
tempSum+=nmb[i]; //累加字段和
}
else //小于0或等于0
{
tempSum=nmb[i];//临时和小于等于0的时候就掐断，即从下一个正数开始再算
beginCout=i;//重置开始计算位置
}
if (tempSum>maxvalue)//零时值如果超过上次储存的最大值
{
maxvalue=tempSum;//存储最大值
endCout=i;//值最大，故重置结束位置
}
}
cout<<"maxvalue="<<maxvalue<<" beginCout="<<beginCout<<" endCout="<<endCout<<endl;
cout<<"MaxValue part is: ";
for (i=beginCout;i<=endCout;i++)//输出
{
cout<<nmb[i]<<" | ";
}
cout<<"\n";
}

㈤最大子段和的分治法

算法描述如下
针对最大子段和这个具体问题本身的结构，我们还可以从算法设计的策略上对上述O(n^2)计算时间算法进行更进一步的改进。从问题的解结构也可以看出，它适合于用分治法求解。
如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种情况：
（1） a[1:n]的最大子段和与a[1:n/2]的最大子段和相同
（2） a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同
（3） a[1:n]的最大子段和为a[i]+…+a[j]，并且1<=i<=n/2，n/2+1<=j<=n。
对于（1）和（2）两种情况可递归求得，但是对于情况（3），容易看出a[n/2]，a[n/2+1]在最大子段中。因此，我们可以在a[1:n/2]中计算出s1=max(a[n/2]+a[n/2-1]+…+a[i]),0<=i<=n/2，并在a[n/2+1:n]中计算出s2= max(a[n/2+1]+a[n/2+2]+…+a[i])，n/2+1<=i<=n。则s1+s2为出现情况（3）的最大子段和。据此可以设计出最大子段和问题的分治算法如下： #include<stdio.h>#defineMAX100intmaxsub(intleft,intright);inta[MAX];intmain(){inti;intcount;scanf(%d,&count);for(i=0;i<count;i++){scanf(%d,&a[i]);}printf(%d/n,maxsub(0,count-1));return0;}intmaxsub(intleft,intright){intcenter,i;intsum,left_sum,right_sum;intleft_max,right_max;center=(left+right)/2;if(left==right)returna[left];else{left_sum=maxsub(left,center);right_sum=maxsub(center+1,right);sum=0;left_max=0;for(i=center;i>=left;i--){sum+=a[i];if(sum>left_max)left_max=sum;}sum=0;right_max=0;for(i=center+1;i<=right;i++){sum+=a[i];if(sum>right_max)right_max=sum;}sum=right_max+left_max;if(sum<left_sum)sum=left_sum;if(sum<right_sum)sum=right_sum;}returnsum;}

㈥最大子段和的介绍

问题：给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。最大子段和是动态规划中的一种。

㈦ C++中最大子段和怎么写（求注释）

#include<iostream>
usingnamespacestd;

intmain()
{
longmaxSum=0,sum=0;
longx,N;

cin>>N;
while(N--)
{
cin>>x;
sum+=x;
//DP
if(sum>maxSum){
maxSum=sum;
}elseif(sum<0){
sum=0;
}
}
cout<<maxSum<<endl;

return0;
}

㈧求最大子列和，用递归方法，有错误，求答案！！！

<pre t="code" l="cpp">#include <stdio.h>

//递归求n！
int func1(int n)
{
if(n==1)
return 1;
else
return func1(n-1)*n;
}
//递归求Fibonacci
int func2(int n)
{
if(n==1 || n==2)
return 1;
else
return func2(n-1)+func2(n-2);
}
//非递归求n！
int func3(int n)
{
int i,sum=1;
for(i=1;i<=n;i++)
{
sum*=i;
}
return sum;
}
//非递归求Fibonacci
int func4(int n)
{
int i,a[100];
a[1]=a[2]=1;
for(i=3;i<=n;i++)
{
a[i]=a[i-2]+a[i-1];
}
return a[n];
}
int main()
{
printf("4!=%d\n",func1(4));
printf("5!=%d\n",func3(5));
printf("f(4)=%d\n",func2(4));
printf("f(6)=%d\n",func4(6));
return 0;
}有问题请追问，

㈨最大子段和问题的算法完整程序

/*简单算法:
**v[0]不保存数据
**T(n)=O(n^2).
*/
int MaxSum(int *v,int n,int *besti,int *bestj)
{
int sum=0;
int i,j;
for (i=1;i<=n;i++)
{
int thissum=0;
for (j=i;j<=n;j++)
{
thissum+=v[j];
if (thissum>sum)
{
sum=thissum;
*besti=i;
*bestj=j;
}
}
}
return sum;
}
/*分治法:
**将a[1n]分成a[1n/2]和a[n/2+1n],则a[1n]的最大字段和有三种情况:
**(1)a[1n]的最大子段和与a[1n/2]的最大子段和相同
**(2)a[1n]的最大子段和与a[n/2n]的最大子段和相同
**(3)a[1n]的最大子段和为ai++aj,1<=i<=n/2,n/2+1<=j<=n
**T(n)=2T(n/2)+O(n)
**T(n)=O(nlogn)
*/
int MaxSum_DIV(int *v,int l,int r)
{
int k,sum=0;
if(l==r)
return v[l]>=0?v[l]:0;
else
{
int center=(l+r)/2;
int lsum=MaxSum_DIV(v,l,center);
int rsum=MaxSum_DIV(v,center+1,r);

int s1=0;
int lefts=0;
for (k=center;k>=l;k--)
{
lefts+=v[k];
if(lefts>s1)
s1=lefts;
}

int s2=0;
int rights=0;
for (k=center+1;k<=r;k++)
{
rights+=v[k];
if(rights>s2)
s2=rights;
}
sum=s1+s2;
if(sum<lsum)
sum=lsum;
if(sum<rsum)
sum=rsum;
}
return sum;
}
/*动态规划算法:
**b[j]=max{a[i]++a[j]},1<=i<=j,且1<=j<=n,则所求的最大子段和为max b[j]，1<=j<=n。
**由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归式为:
**b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。
**T(n)=O(n)
*/
int MaxSum_DYN(int *v,int n)
{
int sum=0,b=0;
int i;
for (i=1;i<=n;i++)
{
if(b>0)
b+=v[i];
else
b=v[i];
if(b>sum)
sum=b;
}
return sum;
}

㈩给定一个整数序列，求出子段序列的最大和，也就是一段连续和元素的和，使其和最大，（如果

#include<stdio.h>

intMaxSum(int*a,intn){

inti,sum=0,max=0;

boolflag1=false,flag2=false;

for(i=0;i<n;i++){

if(a[i]>0)flag1=1;

if(a[i]<0)flag2=1;

}

if(flag1&&flag2){//序列中有正数，也有负数

for(i=0;i<n;i++){

if(a[i]<0){

if(max<sum){

max=sum;

sum=0;

}

elsesum+=a[i];

}

if(max<sum)max=sum;

}

elseif(flag1&&!flag2){//全部为正

for(i=0;i<n;i++)max+=a[i];

}

elseif(!flag1&&flag2){

max=a[0];

for(i=1;i<n;i++){

if(a[i]>max)max=a[i];

}

elsemax=0;//全部为零

returnmax;

}

intmain(){

inta[]={31,-98,45,77,89,12,-92,88,80,120};

for(inti=0;i<10;i++)printf("%d",a[i]);

printf(" MAX=%d ",MaxSum(a,10));

return0;

}

求最大子段和C语言

与求最大子段和C语言相关的内容