最大连续子序列和问题
版权声明：本文为博主原创文章，转载请注明博客地址： https://cloud.tencent.com/developer/article/1433378
第一次看《数据结构与算法分析——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)，贼快。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年09月02日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读