求最大子段和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語言相關的內容