c++ - 最大连续子数组（元素数量最多）

Question

给定一个自然数数组和另一个自然数T，如何找到总和小于或等于T但该子数组中元素个数最大化的连续子数组？

例如，如果给定的数组是：

{3, 1, 2, 1, 1}和T = 5。那么最大连续子数组是{1, 2, 1, 1}因为它将包含 5 个元素并且总和等于 5。

另一个例子：{10,1,1,1,1,3,6,7}用T = 8. 那么最大连续子数组是${1,1,1,1,3}$

我可以通过O(n^2)手术做到这一点。但是我正在为这个问题寻找一个线性时间解决方案。有任何想法吗？

Answer 1

应该可以用 O(n) 做到这一点。我没有对此进行测试，但它看起来不错：

int start = 0, end = 0;
int beststart = 0, bestend = 0;
int sum = array[0];

while (end + 1 < arraysize) {
  if (array[end + 1] + sum <= T)
    sum += array[end++];
  else
    sum -= array[start++];
  if ((end - start) > (bestend - beststart)) {
    beststart = start;
    bestend = end;
  }
}

因此，基本上，它沿着数组移动一个滑动窗口并记录end - start最大的点。

Answer 2

它似乎是最大子数组问题的上限版本：http ://en.wikipedia.org/wiki/Maximum_subarray_problem 我想您可以从现有算法中找到灵感。