3

最大部分列和を解くベントレーの美しいプロラミング パール問題については、誰もが聞いたことがあるでしょう。

maxsofar = 0;
maxcur = 0;
for (i = 0; i < n; i++) {
  maxcur = max(A[i] + maxcur, 0);
  maxsofar = max(maxsofar, maxcur);
}

M より小さい条件最大部分列を追加するとどうなるでしょうか?

4

4 に答える 4

1

これは、疑似多項式時間のみではありますが、動的計画法を使用して解決できます。

定義

m(i,s) := maximum sum less than s obtainable using only the first i elements

max(n,M)次に、次の漸化式を使用して計算できます

m(i,s) = max(m(i-1,s), m(i-1,s-A[i]]+A[i]))

この解決策は、ナップザック問題の解決策に似ています。

于 2011-07-12T16:25:27.247 に答える
1

すべてA[i] > 0の場合、次の手順でこれを行うことができますO(n lg n): 部分和を事前に計算してS[i]から、バイナリ検索Sを行いS[i] + Mます。例えば：

def binary_search(L, x):
  def _binary_search(lo, hi):
    if lo >= hi: return lo
    mid = lo + (hi-lo)/2
    if x < L[mid]:
      return _binary_search(lo, mid)
    return _binary_search(mid+1, hi)
  return _binary_search(0, len(L))

A = [1, 2, 3, 2, 1]
M = 4
S = [A[0]]
for a in A[1:]:
  S.append(S[-1] + a)
maxsum = 0
for i, s in enumerate(S):
  j = binary_search(S, s + M)
  if j == len(S):
    break
  sum = S[j-1] - S[i]
  maxsum = max(sum, maxsum)
print maxsum

編集: atuls が正しく指摘しているように、二分探索はやり過ぎです。S は増加しているので、反復ごとに j を追跡し、そこから先に進むことができます。

于 2011-07-12T16:15:51.650 に答える
1

これはこれを行う必要があります。私はライトですか？

int maxsofar = 0;
for (int i = 0; i < n - 1; i++) {
   int maxcur = 0;
   for (int j = i; j < n; j++) {
      maxcur = max(A[j] + maxcur, 0);
      maxsofar = maxcur < M ? max(maxsofar, maxcur) : maxsofar;
   }
}

残念ながらこれはO(n^2)。の場合、内側のループを壊すことで少し高速化できますがmaxcur >=M、それでもn^2残ります。

于 2011-07-12T16:01:40.933 に答える
0

O(n log(n))で解けます。二分探索木 (平衡型) を使用して sum-M より大きい最小値を検索し、min を更新して、左から右に sum を挿入します。sum はこれまでの部分和です。

  best = -infinity;
  sum = 0;
  tree.insert(0);
  for(i = 0; i < n; i++) {
     sum = sum + A[i];
     int diff = sum - tree.find_smallest_value_larger_than(sum - M);
     if (diff > best) {
       best = diff;
     }
     tree.insert(sum);
   }

   print best
于 2011-07-13T06:19:44.490 に答える