線形配列の場合、連続した番号の最大合計を見つける問題。は簡単だ。Kadane's Algoを使えば簡単にできます。. しかし今、配列は円の形をしており、連続する番号の最大合計を見つける必要があります。したがって、startindex と endindex は配列内のどこにでも置くことができます。時間内に解決する方法がわかりませんO(n)
。
例: { 8, 9, -14, 4, 3}
.
最大部分配列sum= 4+3+8+9= 24. startindex=3 and endindex=1
(ゼロ インデックス配列)。この問題にアプローチする方法について、ヒントまたはアルゴリズムを教えてください。コードは必要ありません。
編集:誰もが述べたように、円形配列は2回スパンする同じ配列に似ています。しかし、その配列に Kadane の Algo を適用し、連続番号を制限する方法。<=nまで