最大子序列问题算法分析.doc
版权申诉
109 浏览量
2022-05-06
12:20:32
上传
评论
收藏 75KB DOC 举报
最大子序列和问题
问题描述：
输入一组整数，求出这组数字子序列和中最大值。也就是只要求出最大子序列的和，
不必求出最大的那个序列。例如：
序列：-2 11 -4 13 -5 -2，则最大子序列和为 20。
序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列和为 16。
算法一：
//穷举法，复杂度O(n^3)
long maxSubSum1(const vector<int>& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
for (int j = i; j < a.size(); j++)
{
long thisSum = 0;
for (int k = i; k <= j; k++)
{
thisSum += a[k];
}
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
这是一个 O(N^3) 的算法，算法本身很容易理解，而且很直观的感觉做了很多无
用操作。例如：i = 0, j = 3 时，会计算 a[0] + a[1] +…+ a[3]；而当 i = 0, j = 4 时候
又会计算 a[0] + a[1] +…a[4]。
算法二：
通过撤出一个 for 循环来避免三次时间。
资源评论
