最大子列和问题的四种不同时间复杂度的算法实现

最近在学习计算机专业课，数据结构课程。在中国大学MOOC网上选修了浙大的《数据结构》课程。最近课程讲到了最大子序列和的问题，结合课程内容、网上的资料借鉴和自己的理解，将解决这个问题的四种不同的算法进行实现和总结。整个工程的代码已经上传。

问题描述：

主函数代码如下：

#include<iostream>
#include<time.h>
using namespace std;

#define NUM_SUM 10
int A[NUM_SUM] = {1, 1, 5, -4, 21, -6, 3, 7, -12, 7};

int MaxSubseqSum1(int A[], int N);
int MaxSubseqSum2(int A[], int N);
int MaxSubseqSum3(int A[], int N);

int MaxSubseqSum4(int A[], int N);
int GetBorderSubseqSum(int A[], int left, int right);

int main()
{
	int maxNum = 0;
	cout <<"系统每秒打点数" << CLK_TCK << endl;

	clock_t tStart,tStop;
	tStart = clock();		//起始时间
	//算法执行1000次
	for(int i=0;i<1000;i++)
		for(int i=0;i<10000;i++)
			maxNum = MaxSubseqSum1(A, NUM_SUM);
	tStop = clock();		//结束时间

	cout << "算法执行时间：" << ((tStop - tStart)/CLK_TCK*1.0/1000) << endl;
	cout << "结果：" << maxNum << endl;
	cin.get();
	cin.get();
	return 0;

}

算法一：暴力求解，时间复杂度：N*N*N。代码实现如下：

//暴力求解
//时间复杂度为： N*N*N
int MaxSubseqSum1(int A[], int N)
{
	int thisNum=0, maxSum=0;
	//左边起始端
	for(int i=0;i<N;i++)
	{
		//右边起始端
		for(int j=i;j<N;j++)
		{
			thisNum =0;
			//索引到中间的每个数据
			for(int k=i;k<=j;k++)
				thisNum +=A[k];
			if(thisNum>maxSum)
				maxSum = thisNum;
		}
	}
	return maxSum;
}

复杂度浪费在第三个for循环。

算法二：时间复杂度：N*N*。代码实现如下：

//复杂度为N*N的算法
int MaxSubseqSum2(int A[], int N)
{
	int thisNum=0, maxSum=0;
	//左边起始端
	for(int i=0;i<N;i++)
	{
		thisNum = 0;	//左边起始端每变化一次，将thisNum置0一次
		//右边起始端
		for(int j=i;j<N;j++)
		{
			thisNum+=A[j];
			if(thisNum>maxSum)
				maxSum = thisNum;
		}
	}
	return maxSum;
}

思想：左边的起始端每变化一次将thisNum置0一次，左边起始端定了，在左边起始端到最右边分别有N-i个不同的子列，但是这些子列起始端都是i的位置，每次左边起始端定了，在后面的N-i个子列中求取和最大的那个值，然后在改变左边的起始端。

算法三：分而治之算法，时间复杂度N*logN。代码实现如下：

/分为治之的思想
//时间复杂度为N*logN
int MaxSubseqSum4(int A[], int N)
{
	//获取左右边界
	int left = 0, right = N-1;

	//只有一个元素
	if(left == right)
	{
		if(A[left]<0)
			return 0;
		else
			return A[left];
	}

	return GetBorderSubseqSum(A, left, right);
}

//将一个小的子列块求其最大列和
//该函数是一个递归调用的函数
int GetBorderSubseqSum(int A[], int left, int right)
{
	//只有一个元素
	if(left == right)
	{
		if(A[left]<0)
			return 0;
		else
			return A[left];
	}
	//获取边界
	int mid = (left+right)/2;
	int nBorderMaxSum = 0;		//左右最大列和值

	//获取左右两快中最大和数
	int nMaxLeftNum = GetBorderSubseqSum(A, left, mid);
	int nMaxRightNum = GetBorderSubseqSum(A, mid+1, right);

	//考虑中间这一一种情况
	//1向左检索
	int nTempMaxLeftSum =0;		//左边检索的最大和值
	int nLeftSum=0;
	for(int i=mid;i>=left;i--)
	{
		nLeftSum +=A[i];
		if(nLeftSum>nTempMaxLeftSum)
			nTempMaxLeftSum=nLeftSum;
	}

	//2、向右检索
	int nTempMaxRightSum =0;		//右边检索的最大和值
	int nRightSum=0;
	for(int i=mid+1;i<=right;i++)
	{
		nRightSum +=A[i];
		if(nRightSum>nTempMaxRightSum)
			nTempMaxRightSum=nRightSum;
	}

	nBorderMaxSum = nTempMaxLeftSum+nTempMaxRightSum;

	//对nBorderMaxSum、nMaxLeftNum、nMaxRightNum三者取最大的
	if(nMaxLeftNum>=nMaxRightNum)
	{
		if(nMaxLeftNum>=nBorderMaxSum)
			return nMaxLeftNum;
		else
			return nBorderMaxSum;
	}

	else
	{
		if(nMaxRightNum>=nBorderMaxSum)
			return nMaxRightNum;
		else
			return nBorderMaxSum;
	}
}

分而治之的思想：就是将一个列分成左右两个部分，左右子列，分别求左右两个子列的最大和数，再求跨越两个子列的最大列和数，最后求三者中的最大值就是所要求的的最大列和数。 注意：这个算法是利用递归的思想，考虑算法的空间复杂度，如果输入的数据量太大，可能造成算法无法运行出正确结果。

关于这个思想的理解，以下截图来自课程中视频：

最大子列和问题的四种不同时间复杂度的算法实现

算法四：在线处理处理算法，时间复杂度：N。代码实现如下：

//在线处理算法,时间复杂度为N
int MaxSubseqSum3(int A[], int N)
{
	int thisNum=0, maxSum=0;
	for(int i=0;i<N;i++)
	{
		thisNum+=A[i];
		if(thisNum>maxSum)
			maxSum = thisNum;
		//如果当前和小于0，则将其丢弃置0，因为其对后面没有作用，只能使后面的更小
		else if(thisNum<0)
			thisNum =0;
	}
	return maxSum;
}

在线的意思是每次输入一个数据就进行即时处理，在任何地方终止输入算法，都能给出正确结果。

秒客网

最大子列和问题的四种不同时间复杂度的算法实现

相关文章