算法笔记——最大子段和问题，最大子矩阵和问题，最大m子段和问题
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;
<
补充：软件开发 , C++ ,
