`
owlman
  • 浏览: 65000 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
最近访客 更多访客>>
社区版块
存档分类
最新评论

【算法】最大子序列问题

阅读更多
本文件实现数组最大子序列问题的四种复杂度的实现。
//立方复杂度
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 最大子序列算法

    C 最大子序列问题的几中算法-分治-联机算法

    C++算法-最大子序列和.zip

    总的来说,最大子序列和问题是一个基础但重要的算法问题,对于理解和掌握动态规划以及迭代方法有着积极作用。通过深入学习C++实现的这一算法,开发者不仅能提升编程技巧,还能锻炼问题解决能力,为解决更复杂的算法...

    最大子序列问题算法分析.doc

    最大子序列问题算法分析 最大子序列问题是计算机科学中的一种经典问题,旨在寻找给定整数序列中最大子序列的和。该问题可以使用多种算法来解决,包括穷举法、递归法等。在本文中,我们将对最大子序列问题的算法进行...

    最大子序列之和C++实现常数时间

    通常,最大子序列和问题通过 Kadane's Algorithm(卡丹算法)可以在线性时间内O(n)解决,但实现常数时间的解决方案则需要特别的优化。然而,应该注意的是,对于大多数情况,常数时间复杂度是不现实的,因为至少需要...

    最大子序列和

    求最大子序列和的四个算法,通过对比,可以了解算法时间计算

    c/c++解决最大子序列和问题

    利用C/C++语言解决最大子列和问题,在线处理-超简单的算法

    最大子序列求和最大子序列求和

    动态规划是解决最大子序列和问题的最优算法之一。其核心思想是利用已计算出的子问题结果,避免重复计算,从而达到优化算法的目的。在这个问题中,我们可以通过维护一个变量,用来存储当前子序列的最大和,每当遇到新...

    最大子序列和问题的求解.md

    ### 最大子序列和问题详解 #### 一、引言 最大子序列和问题是一个经典的计算机科学问题,涉及在一串整数(其中可能包括负数)中找到具有最大和的连续子序列。此问题不仅在理论研究中有重要意义,在实际应用如生物...

    最大子序列和MAX-SUM

    最大子序列和问题,一个整形数组序列求一个不变顺序的相加最大和子序列。

    最大子序列算法[整理].pdf

    最大子序列问题是一种经典的算法问题,它涉及到对一维数组中的连续子序列进行求和,目标是找到和最大的那个子序列。在这个问题中,我们通常使用动态规划的思想来解决。以下是对最大子序列求和算法的详细解释: 1. *...

    最大子序列.pdf

    例如,注释提到的“最大子序列问题”,实际上在代码中似乎是在计算连续子序列的和,而不是找出最大子序列本身。此外,代码中有些地方语法不完整,可能是因为扫描错误,例如`intsum=0;for(i=0;i;i++){}mostEle(num);`...

    西南交通大学-算法分析与设计-实验5.4实验报告包含预习部分-求最大子序列-求最大子矩阵

    最大子序列和问题是一维数组中最长的连续子序列,使得子序列的和最大。最大子矩阵和问题是在二维矩阵中找到一个矩形区域,其内部元素之和最大。 1. **最大子序列和算法**: 在动态规划方法中,我们通常使用Kadane'...

    动态规划算法中对子序列的一些模板

    动态规划是一种强大的算法工具,广泛应用于解决复杂的问题,如寻找最优化路径、组合优化和序列比对等。在本主题“动态规划算法中对子序列的一些模板”中,我们将深入探讨几种与子序列相关的经典问题及其解决方案。 ...

    最大子段和(分治法)源码

    3. Recursive Algorithm:递归算法是一种常用的算法设计方法,通过将原问题划分成更小的子问题,然后递归地解决子问题,最后合并子问题的解来获得原问题的解。 4. 时间复杂性分析:算法的时间复杂性是指算法执行所...

    PHP求最大子序列和的算法实现

    从标签“最大子序列”可以推断出,我们需要关注的是序列中的连续子集,而不是单独的元素,而且我们要找的是这些子集中和最大的那一个。 代码中定义了一个名为`getmaxsum`的函数,它接收一个数组作为参数,然后通过...

    蓝桥杯c++-蓝桥杯竞赛练习之算法提高题和最大子序列.zip

    最大子序列和问题(Maximum Subarray Problem)要求找到一个数组中和最大的连续子数组,最著名的解决方案是 Kadane's Algorithm。该算法通过遍历数组,记录当前和与全局最大和,如果当前元素大于当前和加上前一个...

    算法导论上机报告 算法

    最后,我们讨论最大子序列和问题,这是动态规划的经典案例之一,也被称为“Kadane's Algorithm”。这个问题旨在找到一个数组中的连续子序列,使得其和最大。通过遍历数组,我们可以跟踪到目前为止遇到的最大和以及...

    java实现常见算法

    在 Java 中,实现常见算法是非常重要的,以下是关于链表、约瑟环问题、单链表反转、最大子序列和问题、最大公因数、判断两个数组中是否有相同的数字、字符串反转等知识点的总结。 判断链表是否为循环链表 判断链表...

Global site tag (gtag.js) - Google Analytics