首页
学习
活动
专区
工具
TVP
发布
您找到你想要的搜索结果了吗?
是的
没有找到

算法之路(一)----求最大子序列

优秀的算法甚至能给人amazing的感觉。 今天记录《数据结构与算法分析------C语言描述》中的一个求最大子序列的问题。...问题 给定整数A1,A2,……,AN(可能有负数),设整数k取值i到j(i<=j),求Ai到Aj的和的最大值(所有整数均为负数,则最大子序列和为0)。...后面会给出实际的运行时间,还是先分析和记录算法吧。 算法1 算法1是穷举式的尝试所有的可能,用三重嵌套for循环来求解最大子序列,但是运行的时间非常慢,时间复杂度是O(NNN),即N的立方。...该算法需要有一些分析: 在例子中,最大子序列和可能出现在三处。数据的左半部分,数据的右半部分,或者跨越数据的中部,左右两半部分各占一些。前两种情况可以用递归求解。...分析:该算法首先定义两个变量,maxSum用来记录当前求出的最大子序列和,subSum用来记录遍历的元素中非零和。

49430

大子序列和问题之算法优化

在这个问题中,最大子序列和可能在三处出现:即左半部序列、右半部序列、穿过中部从而占据左右两半部分的序列。前两种情况可以通过递归求解。...故该序列的最大子序列和为max(6,4,0)= 6。 时间复杂度分析: 假设T(n)为求解大小为n的最大子序列和问题所花费的时间。...---- 算法四: 算法三利用递归较好的解决了最大子序列和问题,但仔细分析,在递归过程中,同一个元素很可能多次被操作,有没有更高效的算法?...不仅如此,在任意时刻,该算法都能对它已经读入的数据给出子序列问题的正确答案(其他算法即前三种不具有这个特性)。具有这种特性的算法叫做联机算法(online algorithm)。...仅需要常量空间并以线性时间运行的online algorithm几乎是完美的算法。————《数据结构与算法分析》(中文版第二版)

70730

大子序列和问题之算法优化

在这个问题中,最大子序列和可能在三处出现:即左半部序列、右半部序列、穿过中部从而占据左右两半部分的序列。前两种情况可以通过递归求解。...而递归的基准情况(base cases)是序列只有一个元素(left == right),若该元素大于0,则返回该元素,否则返回0。...故该序列的最大子序列和为max(6,4,0)= 6。 时间复杂度分析: 假设T(n)为求解大小为n的最大子序列和问题所花费的时间。...算法四: 算法三利用递归较好的解决了最大子序列和问题,但仔细分析,在递归过程中,同一个元素很可能多次被操作,有没有更高效的算法?先上代码!...不仅如此,在任意时刻,该算法都能对它已经读入的数据给出子序列问题的正确答案(其他算法即前三种不具有这个特性)。具有这种特性的算法叫做联机算法(online algorithm)。

1.1K70

大子序列

零、前言 最大子序列和问题 这个问题是《数据结构和算法分析》一书中的一个问题,书中给了四种算法 我感觉它是入手算法很不错的一个问题,本文算法源于书中,但文中包含了我的分析和理解 2.题目的分析 也许很多人看到题目就懵圈了...将一个大问题拆解成若干个小问题,使用递归来解决 虽然算法复杂了很多,但运行的时间复杂度降到了O(NlongN),还是很有价值的 最大子序列和可能存在于: 1.左半的序列:maxLeftSum 2.由半的序列...center; i >= start; i--) {//遍历包含center点的侧子序列取最大和 leftBorderSum += a[i]; if (leftBorderSum >...: -2 11 -4 的最大子序列和 |---Q1.2: 13 -5 -2 的最大子序列和 |---Q1.3: 序列和最大值贯穿左右时的最大值: |--- 判断左半:序列含左半最后一个元素的子序列最大值...,也很难去说明这个算法的正确性 这在O(N)的时间完成了最大子序列和问题,这种"简洁和聪明以及高效"也许就是算法的迷人之处。

41430

算法复杂度分析与最大子串问题算法复杂度分析最大子序列问题

算法复杂度分析 算法复杂度基本定义 算法复杂度分析基于以下四条定义: 如果存在常数c与$n_{0}$使$N \geq n_{0} $时,有$T(N) \leq cf(N)$,则记 $T(N) = O(f...判断语句:时间估算为不超过所有分支运算时间之和(与选择耗时的一个分支相同) 循环语句:时间估算为循环次数的乘积(包括嵌套循环) 最大子序列问题 问题 已知一个序列,要求求和最大的连续子序列的和。...例如输入-2,11,-4,13,-5,-2,输出20(11-4+13) 求解 解法一:真.暴力求解 考虑简单直接的解法,计算出以某个数开头的所有子序列和,取出最大的值 func solution1(data...其实前面的和是被重复计算了,计算下一个子序列和时只需要加上结尾的值就可以了。...,找出右侧一半的最大子串,找出跨越左右分界的最大子串(左侧终点确定,右侧起点确定),比较得最大值。

77771

大子序列和O(N)算法简单分析『神兽必读』

对于一个全为负数的序列,最长公共子序列的和值应该是0,理由在于,由0个整数所组成的空子序列也是一个子序列——最大子序列和问题从O(N^3)到线性的算法 其他情况大家也能理解了。...先看算法算法来自《数据结构与算法分析——C语言描述》 int MaxSubsequenceSum(const int A[], int N) { int ThisSum, MaxSum, j;...也是0 为什么不把开头的负数也加和到最大子序列的和中去呢,显然我们做一个假设就很明显了,如-1, 1, 2, 3, 4, 5,没有开头的-1结果更大。...---- UPDATE 或许你会想到了,有时候最大子序列和是某一小段的话,比如是后半段,但是这个算法明显给人的感觉就是一路加和过来呀,好像是认为越长的子序列和越大呀?!...这里继续做一个假设:5, 6,-2, -3,-1, -7,8, 9 明显最大的子序列是8,9,中间跨度的那些负数都不应该加起来,这样的想法的确是对的,但是这个算法也做到了啊。

89020

最大连续子序列和(最大子数组和)四种详细的解法

问题描述:给一个数组,有正有负,求其连续子序列的最大值 解法1:穷举暴力法 枚举左端点跟右端点,然后遍历更新所有的子序列和,最终得到结果就是最大的 #include using...sum); } } cout<<ans<<endl; return 0; } 解法2:单调队列求解 思路:维护一个单调递增的前缀和队列,队首元素是整个序列的最小值...,维护队列的同时,用前缀和的元素减去这个最小值,得到值最大,为这数组的子序列的最大值 #include using namespace std; const int N...= solve4(1,n); cout<<ans<<endl; system("pause"); return 0; } 4.动态规划 思路:这已经是可以用动态规划思想去考虑的简单的问题了...最后我们只需要找出所有最大子段中,最大的那个。

5.1K30
领券