#include
using namespace std;
/*
给定由n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列形如{ak和}i 当所有整数均为负数的时候定义其最大子段和为0。依此定义,所求的最优值为
max{0,max(1 例如,当(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时最大子段和为11 + -4 + 13 = 20
*/
/*
最大子段和的简单求法
*/
/*
int MaxSum( int n, int *a, int &besti, int& bestj )
{
int sum = 0;
for( int i = 1; i {
for( int j = i; j {
int thissum = 0;
for( int k = i; k {
thissum += a[k];
}
//对于每一个i开始到j都求这个序列的和
if ( thissum > sum )
{
sum = thissum;
besti = i;
bestj = j;
}
}
}
return sum;
}
*/
/*
利用已经计算的结果改进算法得到
*/
/*
int MaxSum( int n, int *a, int &besti, int& bestj )
{
int sum = 0;
for( int i = 1; i {
int thissum = 0;
for( int j = i; j {
thissum += a[j];
//利用已经计算好的thissum,避免每次都重复计算
if ( thissum > sum )
{
sum = thissum;
besti = i;
bestj = j;
}
}
}
return sum;
}*/
/*
最大子段和问题的分治算法
针对最大子段问题和这个具体问题,本身的结构,我们可以从算法设计的策略上对上述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:n]的最大子段和相同
(3)a[1:n]的最大子段和为{ak}i (1)(2)两种情形可以递归求得。情形(3),容易看出a[n/2]与a[n/2+1]在最优子序列中。因此
,我们可以在a[1:n/2]中计算出s1 = {1 出s2 = {n/2 + 1 */
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 lefts = 0;
int s = 0;
for( int i = center; i >= left; --i )
{
lefts += a[i];
if ( lefts > s )
{
s = lefts;
}
}
int rights = 0;
int rs = 0;
for( i = center + 1; i < right; ++i )
{
rights += a[i];
if ( rights > rs )
{
rs = rights;
}
}
sum = rs + s;
if ( sum < leftsum )
{
sum = leftsum;
}
if ( sum < rightsum )
{
sum = rightsum;
}
}
return sum;
}
int MaxSum( int n, int *a )
{
return MaxSubSum( a, 1, n );
}
/*
最大子段和问题的动态规划算法
在对上述的分治理算法的分析中,我们注意到,
若记b[j] = {从(1-j)中的下标开始到j的子段和中最大值}{1 也就是以a[j]为结尾的最大子段和
整体最大子段和为:
max{b[j]}{1 因此,当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 */
/*
int MaxSum( int n, int *a, int &besti, int &bestj )
{
int sum = 0;
int b = 0;
int flag = 0;
for( int i = 1; i {
if ( !flag )
{
besti = i;
bestj = i;
flag = 1;
}
if ( b > 0 )
{
b += a[i];
}
else
{
besti = i;
bestj = i;
b = a[i];
}
//calculate b[i]
if ( b > sum )
//record the max b[i] by variable sum
{
bestj = i;
sum = b;
}
}
return sum;
}*/
/*
最大子段和问题与动态规划算法的推广
(1)最大子矩阵和问题:给定一个m行n列的整数矩阵A,试求矩阵A的一个子矩阵
使各元素之和最大。
用二维数组a[1:m][1:n]表示给定的m行n列的整数矩阵。
子数组a[i1:i2][j1:j2]表示左上角
和右下角行列坐标分别为(i1,j1)和(i2,j2)的子矩阵。
注意到
max{1 = max{1 = max{1
其中,t(i1,i2) = max{1 =max{1 设b[j] = a[i][j],
则t(i1,i2) = max{1
//先在同一行内,行范围确定情况下,找出列的最大字段和转换为一维的
//之后再求出行范围的最大字段和,哪些行在一起的总和是最大的
//b[j]记录的就是在行范围确定下第J列的总和
//列方向的最大字段和就是求b[j]的最大字段和,如果b[j]的最大字段和求到,就能确定J的
范围了。之后再求t[i][j]在行上的最大字段和,因为此时J已经确定
*/
int MaxSum2( int m, int n, int **a )
{
int sum = 0;
int *b = new int[n+1];
for( int i = 1; i //1 {
for( int k = 1; k {
b[k] = 0;
}
for( int j = i; j //i {
for( int k = 1; k {
b[k] += a[j][k];
//i1...i2
}
//j是行的增加来决定b数组的增长
int max = MaxSum( n, b );
//b[1]...b[n]的最大子段和
if ( max > sum )
{
sum = max;
//sum的值始终记录的是一个最大的
}
}
}
return sum;
}
/*
最大m子段和问题:
给定由n个整数(可能为负数)组成的序列a1,a2,...,an,以及一个正整数m,
要求确定序列a1,a2,...,an的m个不相交子段
使得这m个子段的总和达到最大。
最大m子段和问题是最大子段和问题在子段个数上的推广。
设b(i,j)表示数组a的前j项中i个子段和的最大值,且第i个子段含a[j](1 则所求的最优值显然为max(m 与最大子段和问题类似地
b(i,j) = max( b(i,j-1) + a[j], max{i-1 其中b(i,j-1)+a[j]项表示第i个子段含a[j-1],
而max{i-1 仅含a[j]。初始时b(0,j) = 0,(1 b(i,0) = 0(1 */
int MaxSumMore( int m, int n, int *a )
{
if ( n < m || m < 1 )
{
return 0;
}
int **b = new int*[m+1];
for( int i = 0; i {
b[i] = new int[n+1];
}
for( i = 0; i {
b[i][0] = 0;
}
for( int j = 1; j {
b[0][j] = 0;
}
for( i = 1; i {
for( int j = i; j //至少要留有n-(m-i)项,如果没有,说明根本不能分成m段,b[i][j]是
//包含a[j]在内的前i个子段的和
{
if ( j > i )
{
b[i][j] = b[i][j-1] + a[j];
//先假设第I个子段包含a[j]
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];
}
//从i-1到j之间找到最大的b[i-1][k],也就是包含i-1个子段和
//的最大的一个
}
}
else
{
b[i][j] = b[i-1][j-1] + a[j];
}
}
}
int sum = 0;
for( j = m; j {
if ( sum < b[m][j] )
{
sum = b[m][j];
}
}
return sum;
}
/*
注意到上述算法中,
计算b[i][j]时只用到数组b的第i-1行和第i行的值。
因而算法中只要存储数组b的当前行,不必存储整个数组。
另一方面,max{i-1 预先保存起来。这样一来,在计算第i行的值时不必重新计算,节省了计算时间和空间。
按此思想可对上述算法
做进一步的改进。
*/
int MaxSumMore1( int m, int n, int *a )
{
if ( n < m || m < 1 )
{
return 0;
}
int *b = new int[n+1];
//b[i]用来记录前i项中最
int *c = new int[n+1];
b[0] = 0;
c[1] = 0;
for( int i = 1; i {
b[i] = b[i-1] + a[i];
//b[i]等同与b[i][i]
c[i-1] = b[i];
//相当前i项中前i-1个子段和的最大值
int max = b[i];
for( int j = i + 1; j {
b[j] = b[j-1] > c[j-1] ? b[j-1] + a[j] : c[j-1] + a[j];
//b[j]等同于b[i][j],前j项中前i个子段的最大和
c[j-1] = max;
//前j-1项中前i-1个子段的和
if ( max < b[j] )
{
max = b[j];
}
}
c[i+n-m] = max;
//前i+n-m项中,前i个子段的最大和
}
int sum = 0;
//b[j]中记录的都是b[m][j]的值
for( int j = m; j {
if ( sum < b[j] )
//b[j]中记录了前j项数据中,m个最大子段和
{
sum = b[j];
}
}
return sum;
}
int main()
{
cout int n = 6;
int *a = new int[n+1];
a[0] = 0;
a[1] = -2;
a[2] = 11;
a[3] = -4;
a[4] = 13;
a[5] = -5;
a[6] = -2;
int besti,bestj;
//int sum = MaxSum( n, a, besti, bestj );
//int sum = MaxSum( n, a );
int sum = MaxSumMore1( 3, 6, a );
cout cout cout
//MaxSum( int m, int n, int *a );
return 0;
}