我知道这非常类似于求最大子数组的和，并且可以在线性时间内完成。这是我几天前听到的一个问题，我想看看如何解决它。
浏览 1提问于2013-01-25得票数 0
回答已采纳
3回答
给出了求连续元素xi，xi+1，···，xj的子序列的O(n)时间算法，其和在所有连续子序列上都是最大的.例如，对于X= {2,5，−10，3，12，−2，10，−7，5}，{3，12，−2，10}是一个解决方案
浏览 12提问于2012-10-05得票数 0
1回答
在我的算法教科书中的dynamic programming章节，我有一个如何使用这种技术解决的例子。我不确定我是否得到了算法背后的想法，所以我将在这里描述我认为它是如何工作的(在多次阅读它并做了几个例子之后)。
基本上，您有一个大小为n的数组A，并且您希望找到该数组的最大子数组和。因此，您递归地调用该函数来计算最大子数组和，从数组的左侧开始，然后从右侧开始。然后，计算从数组中间到末尾的最大子数组和，然后计算从中间到数组开头的最大子数组
浏览 0提问于2015-06-20得票数 0
1回答
节点加权图中的最大N点连通子图
、、、、
以这个节点加权图为例：
我想不出比蛮力更好的方法来获得最大的子图。如果没有已知的有效算法，会不会在这种情况下找到一种遗传<em
浏览 3提问于2013-11-26得票数 0
在解决任何问题时，我们都会编写算法。有的有效率，有的没有，有的工作，有的失败。但有时，当我们进行一次模拟测试时，我们最终会写一些很成功的东西，也许，我们构建测试数据的方式受到了影响，但在其他一些情况下，算法失败了。对于某些算法来说，数据的性质可能是多种多样的，而且数据量很大，例如：
查找包含正数和负数的整数数组的最大子序列和，并返回数组中的开始和结束索引。有人能告诉我，是否有任何特定的通用的经验规则，我们可以设计最严格的测试用例来测试像这样的算
浏览 0提问于2013-04-15得票数 4
回答已采纳
1回答
我遇到了一个在线测试问题，他们给出了一个字符串和每个字符的值。每个字符的值都在- 10，10之间。问题是找到一个以相同字符开头和结尾并具有最大值的子字符串。在用值替换字符后，该问题很容易简化为最大子阵和问题的扩展版本。约束的起始值和结束值是相同的。我想出了一个天真的解决方案，但还不够好。有人能告诉我如何用Kadane的算法或任何其他时间复杂度更高的算法来解决这个问题吗？
浏览 1提问于2020-08-26得票数 0
回答已采纳
我注意到，可以在线性时间内解决的问题，可以调整为使用不超过O(1)辅助空间。取路径图的加权独立集问题。如果只需要总重量，就需要O(1)空间。其它允许线性时间算法的问题有:最大子阵和问题、按i位置旋转一维向量、将BST转换为排序的双链表等。
浏览 2提问于2013-10-14得票数 1
回答已采纳
4回答
设计一个算法来寻找最大的子平方，使得所有4个边界都是黑色的。从左到右扫描每一列，对于每一列中的每个单元格，扫描每一行以找到具有背面边框的最大子方形。
有没有更好的解决方案？
浏览 1提问于2011-11-12得票数 6
回答已采纳
我最初想要一种算法来找到两个python字符串之间最长的子串。基于对线性运行时的在线共识，最佳运行时的一般答案是“构造后缀树”。然而，网上没有任何关于这方面的例子，这并不奇怪，因为后缀树被认为是令人难以置信的复杂和不直观的构造。另外，如果find_longest_match()的算法不是最优的，有谁知道在哪里可以找到如何实现线性最大子</em
浏览 2提问于2013-07-07得票数 0
回答已采纳
2回答
如何找到最大子集T，这样T和S_i的交集I_i (每个0 <= i <= N)最多包含一个元素。
如果没有，是否有一种有效的算法可以找到大子集T
浏览 3提问于2013-10-03得票数 2
回答已采纳
可能重复：
0 -2 -7 0-4 1 -4 1在左下角：-4 1它的总和是15。因此，给定一个矩形，什么是寻找最大子矩形之和的有效算法(在上面的例子中是15)。
浏览 4提问于2010-09-28得票数 3
回答已采纳
以下是问题所在：我们必须使算法在比O(n^2)或O(n*d)更好的时间内运行。所以基本上，它必须是O(nlog(n))，并且分而治之，我认为这是要走的路。我知道如何处理最大连续子数组问题，但这更容易一些，因为当您分而治之时，您可以查找最大子数组，如果有意义的话，您并不知道您在子数组中寻找的是什么，因
浏览 1提问于2015-02-05得票数 1
回答已采纳
4回答
我正在研究用于获取数组中子数组的最大和的算法，并且无法理解代码背后的逻辑。具体来说，这一行max_ending = max(0, max_ending + number)。我不明白这是怎么回事。此外，该算法是否具有O(n)或O(n^2)的复杂性？
浏览 2提问于2015-09-20得票数 0
回答已采纳
2回答
最大子阵列变化
、、
我必须解决一个问题，就像最大子数组问题一样。我必须找到平均值大于k的最大子数组。我想到了下面的技巧。我可以将大小为n的数组A[]转换为B[]，其中Bi = Ai - k，所以现在平均值必须大于0。但是平均值大于零不意味着和大于零吗？所以我可以直接应用Kadane的算法。我说的对吗？(总是在有1个正值的约束下)
浏览 6提问于2012-11-15得票数 1
回答已采纳
2回答
我知道最大子阵和问题及其O(n)算法。这个问题通过使用循环链接列表来修改这个问题：如果所有条目的和为零，那么现在怎么办？对我来说，唯一的方法是修改数组解决方案，并在第一次迭代完成后，让算法循环在列表的开始处重新开始。然后做同样的事情最多2倍的整个列表，并找到最大。不利的一面是，如果我这样做，可能会有很多非常棘手的事情要处理，例如，如果列表看起来是：如果不包含相同的元素两次是非常棘手的谢谢！！
浏览 4提问于2014-09-03得票数 0
2回答
如果可能的话，我希望有人能对算法做一个分析性的解释。例如，给定序列最大子序列和将是这是一个分而治之的算法。
该算法具有O(nlogn)复杂度。实际上，我试图看到这个算法产生的所有步骤的一个例子。上述序列可用于该示例。
浏览 6提问于2011-07-26得票数 6
回答已采纳
我在读“算法导论”。在最大子阵问题(第四章)中，作者认为，单靠求出阵列的最大和最小值，就不能计算买卖股票的最大利润。作者通过计算所有需要0(n^2)时间的买入和卖出日期的组合来讨论诸如蛮力这样的备选方案。另一个选择是在价格数组中找到每日变化的最大子数组。
然而，我编写了一个算法，它将花费0(n)时间并找到最大利润。这是在0(n) vs最大子阵问题0(n log )中。但我知道作者不可能是错的。我哪里出问题了？我的算法正确吗？我以底价为10，算法为A =
浏览 2提问于2016-07-12得票数 0
回答已采纳
2回答
如何寻找和k的最大子阵
、、、、
假设你给出了一个N的数组，它可以有正数和负数。我们需要返回等于k的最大子数组的长度。我尝试使用滑动窗口算法，但很快我发现它在这里不能工作，因为数组元素可以有正负整数。例如：蛮力法采用O(n^2)法，是否有更好的方法来解决同样的问题
浏览 4提问于2022-10-05得票数 0
3回答
背景信息如果我首先运行两种算法，问题大小为5000次，超过10次，递归算法的运行时间从一次运行到下一次，大约减
浏览 0提问于2012-04-01得票数 13
回答已采纳
2回答
我有以下问题要解决，但我不确定该如何解决：输入(这是给定的/您要键入的内容)：每个停车场的值:即-5，0，7，-6，4，3，-5，0，2
输出:应为:3 6 8含义:3-开始批次号，6-结束批次号，8-总利润(7 -6+4+ 3)请帮帮忙。提前谢谢。
编辑
浏览 2提问于2012-06-13得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
