2

O（n）で配列の最大連続サブ配列を見つける方法を知っています。ただし、次のリンクの 2 番目の問題では、一部の要素 (k) を削除できる場合に最大連続サブ配列を見つけることが求められます: http://www.iarcs.org.in/inoi/2011/inoi2011/inoi2011-qpaper.pdf これを行う効率的な方法を見つけることができないようです。

4

2 に答える 2

2

制約を考えると、O(N^2) ソリューションを実行することで十分だと思います。問題の解決方法については説明しませんが、いくつかのヒントを提供します。

  1. 数値の値は非常に限られていることに注意してください - それらは [-10^4, 10^4] の範囲にしかないかもしれません。配列または特定の間隔のみ)
  2. 選択する部分配列の長さを反復し、線形時間で各長さの問題を解決します
  3. 特定の配列では、最小の k 値、またはサブ配列内のすべての負の数が k 未満の場合は常に破棄されることに注意してください。

これが問題の解決に役立つことを願っています。

于 2012-12-31T10:26:08.607 に答える
1

O(NK) 動的計画法ソリューションがあります。

d[i][j](0<= < i=N, 0<= <=K) は、要素を削除することにより、要素 thjで終わる任意の (空の可能性がある) サブ配列の最大合計になります。ij

初期値: d[0][j] = 00<= j<=Kの場合

動的値の更新:

for i = 1 to N:
     d[i][0] = max (d[i-1][0]+a[i], 0)
     for j = 1 to K:
         d[i][j] = max(d[i-1][j]+a[i], d[i-1][j-1])

解はmax{d[N][j]}0<= j<=Kの場合です

于 2012-12-31T14:12:31.340 に答える