消除最大子數組

我知道如何在O（n）中找到數組的最大連續子數組。但是，當下面的鏈接中的第二個問題要求在某些元素（k）可以消除時找到最大的連續子數組： http://www.iarcs.org.in/inoi/2011/inoi2011/inoi2011-qpaper.pdf 我似乎無法找到一種有效的方法來完成此操作。消除最大子數組

來源

2012-12-31 Shivam Gupta

你能告訴你的低效率的方式？ – rene

如果您瞭解連續子數組解決方案的工作原理，那麼您應該可以對連續子數組與連續子空間情況稍微進行修改。後者的複雜性實際上是O（N log K）。沒有更多的提示，這個數字是一個死的贈品。 –

查看您的評論後，問題變得非常容易。感謝提示 –

考慮到我認爲要做一個O（N^2）解決方案的限制。我不會告訴你如何解決這個問題，但會給你一些提示：

注意，號碼價值相當有限 - 他們可能只是在區間[-10^4，10^4]這使得有可能有一個數組，您可以計算給定值（整個數組中或僅在給定的時間間隔內）有多少個數字
迭代您將選擇的子數組的長度並解決問題每個長度在線性時間
請注意，對於給定的數組，您將始終丟棄最小的k值或子數組中的所有負數，如果它們小於k

希望這會幫助你解決問題。

來源

2012-12-31 10:26:08

'給定約束條件，我認爲做一個O（N^2）解決方案會做'在最壞的情況下，N可以是10^4 - 這有點臨界並且可能沒有超過時間限制。 – nhahtdh

@nhahtdh我通常會在2秒的時間內使用N^2解決方案。我所見過的大多數在線評委系統甚至在2秒內通過10億次或更多的操作。我相信這個解決方案將足夠快。另外請注意，我提出的解決方案非常簡單，因此它只使用大約2 * 10^8 **簡單**操作。我應該相信。 –

如果你這麼說的話，這樣的公平就夠了 - 我很少冒險靠近時間限制，所以我不知道。 – nhahtdh

有一個O（NK）動態規劃溶液：

讓d[i][j]（0 < i = < = N，0 < j = = < K）是任何（可能爲空）的最大總和子數組以i th元素結尾，刪除j元素。

初始值： d[0][j] = 0爲0 < = 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-31 14:12:31 mhsekhavat

消除最大子數組

回答

相關問題