c – 最大连续子阵列(具有大多数元素)

发布时间：2020-12-16 07:35:18 所属栏目：百科来源：网络整理

导读：给定一个自然数和另一个自然T的数组,如何找到小于或等于T的连续子阵列但该子阵列中的元素数量最大化？例如,如果给定的数组是： {3,1,2,1}和T = 5.然后最大的重叠子阵列是{1,1},因为它将包含5个元素,并且总和等于5. 另一个例子：{10,3,6,7},T = 8.那么最大的

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

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

{3,1,2,1}和T = 5.然后最大的重叠子阵列是{1,1},因为它将包含5个元素,并且总和等于5.

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

我可以用O(n ^ 2)操作来做.但是,我正在寻找这个问题的线性时间解决方案.有任何想法吗？

解决方法

应该可以用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;
  }
}

因此,基本上,它沿着数组移动一个滑动窗口,并记录结束 – 开始最大的点.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!