本文件实现数组最大子序列问题的四种复杂度的实现。
//立方复杂度
int maxsubsum1(int *array,size_t sz)
{
int maxsum = array[0];
for(size_t i = 0; i < sz; ++i)
for(size_t j = i; j < sz; ++j)
{
int thissum = 0;
for(size_t k = i; k <= j; ++k)
thissum += array[k];
if(thissum > maxsum)
maxsum = thissum;
}
return maxsum;
}
//平方复杂度
int maxsubsum2(int *array,size_t sz)
{
int maxsum = array[0];
for(size_t i = 0; i < sz; ++i)
{
int thissum = 0;
for(size_t j = i; j < sz; ++j)
{
thissum += array[j];
if(thissum > maxsum)
maxsum = thissum;
}
}
return maxsum;
}
//分治法(O(NlogN)复杂度)
int maxsubsum3(int *array,int left,int right)
{
if(left == right)
return array[left];
int mid = (right+left) / 2;
int rthissum=0,lthissum=0,
rmaxsum=0,lmaxsum=0;
int lmax = maxsubsum3(array,left,mid);
int rmax = maxsubsum3(array,mid+1,right);
for(int i = mid; i >= left; --i)
{
lthissum += array[i];
if(lthissum > lmaxsum)
lmaxsum = lthissum;
}
for(int i = mid+1; i <= right; ++i)
{
rthissum += array[i];
if(rthissum > rmaxsum)
rmaxsum = rthissum;
}
int max = rmaxsum + lmaxsum;
if(max >= rmax)
if(max >= lmax)
return max;
else
return lmax;
else if(rmax >= lmax)
return rmax;
else
return lmax;
}
//线性复杂度
int maxsubsum4(int *array,size_t sz)
{
int maxsum=array[0],thissum=0;
for(size_t i = 0; i < sz; ++i)
{
thissum += array[i];
if(thissum > maxsum)
maxsum = thissum;
else if(thissum < 0)
thissum = 0;
}
return maxsum;
}
分享到:
相关推荐
动态规划算法:最大子序列问题
2010.09.07 用分治法求解最大子序列问题。...《数据结构与算法分析 C++描述》p42最大子序列问题的递归方法代码 2010.09.07 vector a的内容: 4 -3 5 -2 -1 2 6 -2 最大子序列和是:11 请按任意键继续. . .
C 最大子序列问题的几中算法-分治-联机算法
最大子序列问题算法分析.doc
C++算法_最大子序列和.zip
求最大子序列和的四个算法,通过对比,可以了解算法时间计算
利用C/C++语言解决最大子列和问题,在线处理-超简单的算法
最大子序列算法[整理].pdf
最大子序列和问题,一个整形数组序列求一个不变顺序的相加最大和子序列。
例如: 序列(-2,11,-4,13,-5,-2)的最大子序列和为20序列; (-6,2,4,-7,5,3,2,-1,6,-9,10,-2)的最大子序列和为16。 3.用分治策略求众数问题 问题描述:给定含有n个元素的多重集合S,每个元素在...
采用java语言实现了寻找最大子序列的算法, 主要用到了动态规划的思想。
php //作者:遥远的期待 //QQ:15624575 //算法分析:1、必须是整数序列、2、如果整个序列不全是负数,最大子序列的第一项必须是正数,否则最大子序列后面的数加起来再加上第一项的负数,其和肯定不是最大的;...
实序列FFT算法的C语言实现,文档写得非常详细,里面含有c程序代码及讲解,通俗易懂
活动选择(Activity Selection) 备选列表排列(Alternative List Arrange) Davis–Putnam–Logemann–Loveland算法 Dijkstra银行家算法(Dijkstra ...最大子序列(Maximum Subsequence) 嵌套括号(Nested Brackets
4.1 最大子数组问题 4.2 矩阵乘法的Strassen算法 4.3 用代入法求解递归式 4.4 用递归树方法求解递归式 4.5 用主方法求解递归式 4.6 证明主定理 4.6.1 对b的幂证明主定理 4.6.2 向下取整和...
用分治法求最大子段和,适合刚接触数据结构的初学者
算法分析2.1 数学基础2.2 模型2.3 要分析的问题2.4 运行时间计算2.4.1 一个简单的例子2.4.2 一般法则2.4.3 最大子序列和问题的解2.4.4 运行时间中的对数2.4.5 检验你的分析2.4.6 分析结果的准确性总结练习第3章 ...
2.4.3 最大子序列和问题的解 2.4.4 运行时间中的对数 2.4.5 检验你的分析 2.4.6 分析结果的准确性 小结 练习 参考文献 第3章 表、栈和队列 3.1 抽象数据类型(ADT) ...