我正在尝试实现一个方法来获得maxSubArray和以及相关的开始和结束索引。作为参考,maxSubArray是所有子数组中整数和最大的连续子数组。我的和正确,结束索引正确,但我有麻烦得到开始。我已经说明了一个小案件,但无论我做什么,我似乎不能解释所有的案件。每当我解释一个,另一个就会出现。显然,在线性时间内求和是可能的,但我似乎无法找到一种有效地获得正确的起始索引的方法。在
def maxSubArray(seq):
#max_i = max ending at i, max_gen = best max up until i
max_i = max_gen = beg = end = prev_max = 0
for i in xrange(len(seq)):
#use dynamic programming to get maxSubArray sum (works)
max_i = max(0, max_i + seq[i])
max_gen = max(max_gen, max_i)
#get correct end (works)
if prev_max < max_gen:
end = i
prev_max = max_gen
if max_gen == 0:
max_gen = max(seq)
beg = end = seq.index(max_gen)
return [max_gen, beg, end]
就像我说的,我尝试了很多东西,但是不断地删除它们,因为每一个新的方法都会带来新的/旧的问题。有人有什么建议/解决办法吗?我在Java标签下看到了一个类似的问题,但答案并不正确。为了方便起见,我提供了一个强力方法,我知道它是有效的,以及我一直在使用的迷你测试仪:
^{2}$
恕我直言,这很管用,而且是Python式的。在
算法是一样的。对于在这里结束的数组(
cur_
)和整体(all_
),有sum、起始索引和结束索引。在编辑:注意这里的结束索引是排他的。在
另外,如果有多个最优子阵列,则返回第一个和最长的子阵列。在
这个问题对我来说似乎很熟悉。。。快速搜索发现了一篇维基百科文章Maximum subarray problem。改编自本文中的c++解决方案
相关问题 更多 >
编程相关推荐