[C++知识库]求解最大序列和问题（C++）

最大序列和问题是给定一段序列，求出这个序列中挨到一起的数字，它们通过相加得出的最大值。由于本人是刚入学的萌新，第一次所想到的办法是通过暴算穷举出所有组合它们构成的数，然后中出其中最大值。显然，完成这个算法需要两点：
1.穷举所有组合

2.求出最大值

我的思路非常浅显以至于幼稚，是按照小学所学的办法，依照一个数相加、两个数相加、......这样的特点来分类，我所编写的程序中ListMax函数中的变量i就是说当前所计算情况是由i个数相加。在这个函数中，我利用循环来生成所有可能的个数相加的情况。至于每一种情况具体又包含哪些具体组合，在这些组合中哪个又是最大的，则通过ContinuousSum函数来实现，所得的结果传回ContinuousSum函数，再找出最大值，此即为结果。参考程序如下，欢迎广大大佬斧正：

#include<iostream>
using namespace std;
int ContinuousSum(int *p, int i, int N)
{
	int sum0 = 0;
	int now = 0;
	for(int j=0; j<N-i+1; j++)
	{
		for(int k=j; k<i+j; k++)
		{
			now = now + p[k]; 
		}
		if(now > sum0)
		{
			sum0 = now;
		}
		now = 0;
	}
	return sum0;
}
int ListMax(int a[], int N)
{
	int sum = 0;
	for(int i=1; i<=N; i++)
	{
		if(ContinuousSum(a, i, N)>sum)
		{
			sum = ContinuousSum(a, i, N);
		}
	}
	return sum;
}
int main()
{
	int N;
	cin>>N;
	int a[N];
	for(int i=0; i<N; i++)
	{
		cin>>a[i];
	}
	cout<<"最大序列和为: "<<ListMax(a, N)<<endl;
	return 0;
}

本算法缺点：

1.本算法太幼稚，容易被骂。

2.本算法的分类方式不易于算法的发展，它按照相加数的个数来分类，注定了如：一个数相加的组合和一个数相加的组合在一起，而分隔了一个数相加的组合和两个数、三个数......相加的组合，使得个数少的组合的数据无法通过累加来供“后世”免去重复之苦，大大增加了不必要的计算。参考马克·艾伦·维斯教授所著《数据结构与算法分析》一书，它对此问题的解决方案中的第一个算法的分类方式就有利于衍生出后来更加高效的算法：它以序列中每一个数为分类基点，第一个数就是第一类的最高层，依次往下是：第一个数加第二个数、第一个数加第二个数加第三个数......即使在算法一中每一次循环求和ThisSum会被莫名其妙的释放，下一次循环令为0，但这样确实为算法提供了上升空间。（为方便阅读现将书中第一代算法贴在下面）

int
MaxSubsequenceSum( const int A[ ], int N )
{
    int ThisSum, MaxSum, i, j, k;

    MaxSum = 0;
    for( i = 0; i < N; i++ )
        for( j = i; j < N; j++ )
        {
            ThisSum = 0;
            for( k = i; k <= j; k++ )
                ThisSum += A[ k ];

            if( ThisSum > MaxSum )
                MaxSum = ThisSum;
        }
    return MaxSum;
}

本问题解决途中可以看出我的编程思维还是停留在小学阶段，希望日后能不断进步；同时也希望我所编写的这个对小白来说比较友好的程序可以抛砖引玉，激发大家共同努力。