最大连续子序列和问题

版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.net/zy010101/article/details/82315888

第一次看《数据结构与算法分析——C语言描述》这本书的时候,被书中一上来就给的最大子序列和问题给直接镇住了。直观感觉就是好难,好牛逼。

问题描述:给定整数k1,k2,k3,...,kn,求从第i个数到第j个数的最大值。(如果所有整数均为负数,那么最大子序列和规定为0)

根据题目描述,最直接的算法就是穷举所有的从i到j的和,比较它们的大小,留下最大的那个和,就是我们所求的最大子序列和。

算法1:暴力穷举法

int MaxSubsequenceSum(const vector<int>& num, int n)
{
	int thissum, i, j, k, maxsum;
	maxsum = 0;
	for ( i = 0; i < n; i++)
	{
		for ( j = i; j < n; j++)
		{
			thissum = 0;
			for ( k = i; k <= j; k++)        //穷举计算从i到j个数的和
			{
				thissum += num[k];
			}
			if (thissum > maxsum)
			{
				maxsum = thissum;
			}
		}
	}
	return maxsum;
}

它的时间复杂度是O(n³),这个时间复杂度很大。不是一个好的算法。

算法2:简化求和

int MaxSubsequenceSum(vector<int> &num, int n)
{
	int thissum, i, j, maxsum;
	maxsum = 0;
	for ( i = 0; i < n; i++)
	{
		thissum = 0;
		for ( j = i; j < n; j++)
		{    //对上面算法计算和的过程进行了简化
			thissum += num[j];
			if (thissum > maxsum)
			{
				maxsum = thissum;
			}
		}
	}
	return maxsum;
}

它相对于算法1就快了许多,它的时间复杂度是O(n²)。当然我们说一般而言这种时间复杂度也不是一个好的算法。

算法3:联机算法(online algorithm)

int MaxSubsequenceSum(const vector<int>& num, int n)
{
	int thissum, maxsum, i;
	maxsum = thissum = 0;
	for ( i = 0; i < n; i++)
	{
		thissum += num[i];
		if (thissum > maxsum)
		{
			maxsum = thissum;
		}
		if (thissum < 0)		//规定如果是负数,则最大值为0;
		{
			thissum = 0;
		}
	}
	return maxsum;
}

这个算法的时间复杂度是O(n),贼快。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券