Q

查找最大总数连续子数组，使得子数组的长度小于等于k？

2016-08-13 63 views 0 likes

0

如果存在两个以上的子数组，我们需要返回长度较小的子数组。查找最大总数连续子数组，使得子数组的长度小于等于k？

我们只关心子数组的长度及其总和。

我知道这可以在使用蛮力O（n^2）中解决，但我正在寻找一种有效的方法来做到这一点。我也尝试使用滑动窗口概念在O（n）中解决这个问题，但后来我意识到它在某些情况下失败了。

这怎么能有效地完成？

2016-08-13 A. Sam

+0

也许我是唯一需要这种帮助的读者（或者需要它使我无法回答），但输入数据结构是什么？一组数字？什么是连续的子阵列？ – danh

+0

@danh“连续”一词表示相邻或相邻。连续的子阵列具有彼此相邻的所有元素。类似的，对于10个元素的数组，a [0]，a [1]，a [2]构成一个连续的子数组，a [0]，a [2]，[4] dont –

A

回答

1

我建议你看看Kadane的算法。它从给定的数组中找到一个连续的子数组。它在O（n）中这样做。您的问题将长度限制为“k”。所以你只需要在Kadane's中检查长度< = k。

2016-08-14 05:08:58

相关问题