algorithm - 找到最大和连续子数组，使得子数组的长度小于等于 k？

Question

如果存在两个以上的子数组，我们需要返回长度较小的子数组。

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

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

如何有效地做到这一点？

Answer 1

我建议你看看 Kadane 的算法。它从给定数组中找到一个总和最大的连续子数组。它在 O(n) 中这样做。您的问题将长度限制为“k”。因此，您只需在 Kadane 中检查长度 <= k。