1、最大子段和問題
問題定義：對於給定序列a1,a2,a3……an,尋找它的某個連續子段，使得其和最大。如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和為20。
(1)枚舉法求解
枚舉法思路如下：
以a[0]開始: {a[0]}, {a[0],a[1]},{a[0],a[1],a[2]}……{a[0],a[1],……a[n]}共n個
以a[1]開始: {a[1]}, {a[1],a[2]},{a[1],a[2],a[3]}……{a[1],a[2],……a[n]}共n-1個
……
以a[n]開始:{a[n]}共1個
一共(n+1)*n/2個連續子段，使用枚舉，那麼應該可以得到以下算法：
具體代碼如下：
[cpp]
//3d4-1 最大子段和問題的簡單算法
#include "stdafx.h"
#include <iostream>
using namespace std;
int MaxSum(int n,int *a,int& besti,int& bestj);
int main()
{
int a[] = {-2,11,-4,13,-5,-2};
for(int i=0; i<6; i++)
{
cout<<a[i]<<" ";
}
int besti,bestj;
cout<<endl;
cout<<"數組a的最大連續子段和為：a["<<besti<<":"<<bestj<<"]:"<<MaxSum(6,a,besti,bestj)<<endl;
return 0;
}
int MaxSum(int n,int *a,int& besti,int& bestj)
{
int sum = 0;
for(int i=0; i<n; i++)//控制求和起始項
{
for(int j=i; j<n; j++)//控制求和結束項
{
int thissum = 0;
for(int k=i; k<=j; k++)//求和
{
thissum += a[k];
}
if(thissum>sum)//求最大子段和
{
sum = thissum;
besti = i;
bestj = j;
}
}
}
return sum;
}
從這個算法的三個for循環可以看出，它所需要的計算時間是O(n^3)。事實上，如果注意到，則可將算法中的最後一個for循環省去，避免重復計算，從而使算法得以改進。改進後的代碼如下：
[cpp] 的避免重復的簡單算法
#include "stdafx.h"
#include <iostream>
using namespace std;
int MaxSum(int n,int *a,int& besti,int& bestj);
int main()
{
int a[] = {-2,11,-4,13,-5,-2};
for(int i=0; i<6; i++)
{
cout<<a[i]<<" ";
}
int besti,bestj;
cout<<endl;
cout<<"數組a的最大連續子段和為：a["<<besti<<":"<<bestj<<"]:"<<MaxSum(6,a,besti,bestj)<<endl;
return 0;
}
int MaxSum(int n,int *a,int& besti,int& bestj)
{
int sum = 0;
for(int i=0; i<n; i++)//控制求和起始項
{
int thissum = 0;
for(int j=i; j<=n; j++)//控制求和結束項
{
thissum += a[j];//求和
if(thissum>sum)
{
sum = thissum;
besti = i;
bestj = j;
}
}
}
return sum;
}
(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]的最大字段和為，且1<=i<=n/2,n/2+1<=j<=n。
可用遞歸方法求得情形[1],[2]。對於情形[3],可以看出a[n/2]與a[n/2+1]在最優子序列中。因此可以在a[1:n/2]中計算出，並在a[n/2+1:n]中計算出。則s1+s2即為出現情形[3]時的最優值。
具體代碼如下：
[cpp]
//3d4-1 最大子段和問題的分治算法
#include "stdafx.h"
#include <iostream>
using namespace std;
int MaxSubSum(int *a,int left,int right);
int MaxSum(int n,int *a);
int main()
{
int a[] = {-2,11,-4,13,-5,-2};
for(int i=0; i<6; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"數組a的最大連續子段和為:"<<MaxSum(6,a)<<endl;
return 0;
}
int MaxSubSum(int *a,int left,int right)
{
int sum = 0;
if(left == right)
{
sum = a[left]>0?a[left]:0;
}
else
{
int center = (left+right)/2;
int leftsum = MaxSubSum(a,left,center);
int rightsum = MaxSubSum(a,center+1,right);
int s1 = 0;
int lefts = 0;
for(int i=center; i>=left;i--)
{
lefts += a[i];
if(lefts>s1)
{
s1=lefts;
}
}
int s2 = 0;
int rights = 0;
for(int i=center+1; i<=right;i++)
{
rights += a[i];
if(rights>s2)
{
s2=rights;
}
}
sum = s1+s2;
if(sum<leftsum)
{
sum = leftsum;
}
if(sum<rightsum)
{
sum = rightsum;
}
}
return sum;
}
int MaxSum(int n,int *a)
{
return MaxSubSum(a,0,n-1);
}
算法所需的計算時間T(n)滿足一下遞歸式：
解此遞歸方程可知：T(n)=O(nlogn)。
(3)動態規劃算法求解
算法思路如下：
記，則所求的最大子段和為：
由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。
具體代碼如下：
[cpp]
//3d4-1 最大子段和問題的動態規劃算法
#include "stdafx.h"
#include <iostream>
using namespace std;
int MaxSum(int n,int *a);
int main()
{
int a[] = {-2,11,-4,13,-5,-2};
for(int i=0; i<6; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"數組a的最大連續子段和為:"<<MaxSum(6,a)<<endl;
return 0;
}
int MaxSum(int n,int *a)
{
int sum=0,b=0;
for(int i=1; i<=n; i++)
{
if(b>0)
{
b+=a[i];
}
else
{
b=a[i];
}
if(b>sum)
{
sum = b;
}
}
return sum;
}
上述算法的時間復雜度和空間復雜度均為O(n)。
2、最大子矩陣和問題
(1)問題描述：給定一個m行n列的整數矩陣A，試求A的一個子矩陣，時期各元素之和為最大。
(2)問題分析：
用二維數組a[1:m][1:n]表示給定的m行n列的整數矩陣。子數組a[i1:i2][j1:j2]表示左上角和右下角行列坐標分別為(i1,j1)和(i2,j2)的子矩陣，其各元素之和記為：
最大子矩陣問題的最優值為。如果用直接枚舉的方法解最大子矩陣和問題，需要O(m^2n^2)時間。注意到，式中，，設，則
容易看出，這正是一維情形的最大子段和問題。因此，借助最大子段和問題的動態規劃算法MaxSum，可設計出最大子矩陣和動態規劃算法如下:
[cpp]
//3d4-5 最大子矩陣之和問題
#include "stdafx.h"
#include <iostream>
using namespace std;
const int M=4;
const int N=3;
int MaxSum(int n,int *a);
int MaxSum2(int m,int n,int a[M][N]);
int main()
{
int a[][N] = {{4,-2,9},{-1,3,8},{-6,7,6},{0,9,-5}};
for(int i=0; i<M; i++)
{
for(int j=0; j<N; j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
cout<<"數組a的最大連續子段和為:"<<MaxSum2(M,N,a)<<endl;
return 0;
}
int MaxSum2(int m,int n,int a[M][N])
{
int sum = 0;
int *b = new int[n+1];
for(int i=0; i<m; i++)//枚舉行
{
for(int k=0; k<n;k++)
{
b[k]=0;
}
for(int j=i;j<m;j++)//枚舉初始行i,結束行j
{
for(int k=0; k<n; k++)
{
b[k] += a[j][k];//b[k]為縱向列之和
int max = MaxSum(n,b);
if(max>sum)
{
sum = max;
}
}
}
}
return sum;
}
int MaxSum(int n,int *a)
{
int sum=0,b=0;
for(int i=1; i<=n; i++)
{
if(b>0)
{
b+=a[i];
}
else
{
b=a[i];
}
if(b>sum)
{
sum = b;
}
}
return sum;
}
以上代碼MaxSum2方法的執行過程可用下圖表示：
3、最大m子段和問題
(1)問題描述：給定由n個整數(可能為負數)組成的序列a1,a2,a3……an,以及一個正整數m,要求確定此序列的m個不相交子段的總和達到最大。最大子段和問題是最大m字段和問題當m=1時的特殊情形。
(2)問題分析：設b(i,j)表示數組a的前j項中i個子段和的最大值，且第i個子段含a[j](1<=i<=m,i<=j<=n),則所求的最優值顯然為。與最大子段問題相似，計算b(i,j)的遞歸式為：
其中，表示第i個子段含a[j-1],而項表示第i個子段僅含a[j]。初始時，b(0,j)=0,(1<=j<=n);b(i,0)=0,(1<=i<=m)。
具體代碼如下：
[cpp]
//3d4-6 最大m子段問題
#include "stdafx.h"
#include <iostream>
using namespace std;
int MaxSum(int m,int n,int *a);
int main()
{
int a[] = {0,2,3,-7,6,4,-5};//數組腳標從1開始
for(int i=1; i<=6; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"數組a的最大連續子段和為:"<<MaxSum(3,6,a)<<endl;
}
int MaxSum(int m,int n,int *a)
{
if(n<m || m<1)
return 0;
int **b = new int *[m+1];
for(int i=0; i<=m; i++)
{
b[i] = new int[n+1];
}
for(int i=0; i<=m; i++)
{
b[i][0] = 0;
}
for(int j=1;j<=n; j++)
{
b[0][j] = 0;
}
//枚舉子段數目，從1開始，迭代到m，遞推出b[i][j]的值
for(int i=1; i<=m; i++)
{
//n-m+i限制避免多余運算，當i=m時，j最大為n，可據此遞推所有情形
for(int j=i; j<=n-m+i; j++)
{
if(j>i)
{
b[i][j] = b[i][j-1] + a[j];//代表a[j]同a[j-1]一起，都在最後一子段中
for(int k=i-1; k<j; k++)
{
if(b[i][j]<b[i-1][k]+a[j])
b[i][j] = b[i-1][k]+a[j];//代表最後一子段僅包含a[j]
}
}
else
{
b[i][j] = b[i-1][j-1]+a[j];//當i=j時，每一項為一子段
}
}
}
int sum = 0;
for(int j=m; j<=n; j++)
{
if(sum<b[m][j])
{
sum = b[m][j];
}
}
return sum;
}
上述算法的時間復雜度為O(mn^2)，空間復雜度為O(mn)。其實，上述算法中，計算b[i][j]時，只用到了數組b的第i-1行和第i行的值。因而，算法中只要存儲數組b的當前行，不必存儲整個數組。另一方面，的值可以在計算i-1行時預先計算並保存起來。計算第i行的值時不必重新計算，節省了計算時間和空間。因此，算法可繼續改進如下：
[cpp]
//3d4-7 最大m子段問題
#include "stdafx.h"
#include <iostream>
using namespace std;
int MaxSum(int m,int n,int *a);
int main()
{
int a[] = {0,2,3,-7,6,4,-5};//數組腳標從1開始
for(int i=1; i<=6; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"數組a的最大連續子段和為:"<<MaxSum(3,6,a)<<endl;
}
int MaxSum(int m,int n,int *a)
{
if(n<m || m<1)
return 0;
int *b = new int[n+1];
int *c = new int[n+1];
b[0] = 0;//b數組記錄第i行的最大i子段和
c[1] = 0;//c數組記錄第i-1行的最大i-1子段和
for(int i=1; i<=m; i++)
{
b[i] = b[i-1] + a[i];
c[i-1] = b[i];
int max = b[i];
//n-m+i限制避免多余運算，當i=m時，j最大為n，可據此遞推所有情形
for(int j=i+1; j<=i+n-m;j++)
{
b[j] = b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];
c[j-1] = max;//預先保存第j-1行的最大j-1子段和
if(max<b[j])
{
max = b[j];
}
}
c[i+n-m] = max;
}
int sum = 0;
for(int j=m; j<=n; j++)
{
if(sum<b[j])
{
sum = b[j];
}
}
return sum;
}
上述算法時間復雜度為O(m(n-m))，空間復雜度為O(n)。當m或n-m為常數時，時間復雜度和空間復雜度均為O(n)。
