4

自然数の配列と別の自然Tが与えられた場合、合計がT以下であるが、このサブ配列の要素数が最大化されている連続したサブ配列を見つけるにはどうすればよいですか？

たとえば、指定された配列が次の場合：

{3, 1, 2, 1, 1}およびT = 5。次に、最大の連続サブアレイは{1, 2, 1, 1}、5つの要素を含み、合計が5に等しいためです。

別の例：{10,1,1,1,1,3,6,7}with T = 8。その場合、最大の隣接サブアレイは次のようになります。${1,1,1,1,3}$

操作でできますO(n^2)。しかし、私はこの問題の線形時間解を探しています。何か案は？

4

2 に答える 2

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;
  }
}

したがって、基本的には、配列に沿ってスライディング ウィンドウを移動しend - start、最大のポイントを記録します。

于 2013-03-04T17:12:31.717 に答える
0

これは、最大部分配列問題の制限付きバージョンのようです: http://en.wikipedia.org/wiki/Maximum_subarray_problem 既存のアルゴリズムでインスピレーションを見つけることができると思います。

于 2013-03-04T17:07:41.420 に答える