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 最大的点。