與長度約束

最大子陣我問這個了在CS.SE，但沒有得到迴應。與長度約束

我最近面臨以下面試問題：

給定一個數組A和整數k，找到與最大總和的連續子陣列，與所添加的約束此子陣列具有長度在最k。

所以，如果A=[8, -1, -1, 4, -2, -3, 5, 6, -3]那麼我們得到以下答案爲k不同的值：

+---+------------------------------+ 
| k |   subarray   | 
+---+------------------------------+ 
| 1 | [8]       | 
| 7 | [5,6]      | 
| 8 | [8, -1, -1, 4, -2, -3, 5, 6] | 
+---+------------------------------+

如果n是數組A的長度，然後用修改的優先級隊列，我能及時回答這個問題O(n lgk);有沒有辦法將此改進爲O(n)？請注意，當k = n時，Kadane的算法在O(n)時間內運行。

來源

2015-09-11 Steve D

如果你限制你保持與K跟蹤數組的大小如何Kadane的算法失敗？ –

@ G.Bach：當k = 7時，試着爲問題中的數組做準備。當你到達'5'時，最後一個數組結尾是'[8，-1，-1，4，-2，-3，5]'。但是，當你移動到'6'時，你需要放下'8';這會導致連鎖反應降低'-1，-1，4，-2，-3'，因爲長度最大的子陣列最多7個，結束於'6'，是'[5,6]'。換句話說，當你走陣列時，你需要跟蹤哪些元素「掉落」，而一個天真的實現導致時間與n * k成比例。 –

你確定？你會有兩個指針，一個左邊一個右邊，每個都會遍歷數組一次，不是嗎？ –

可以在O（n）的做到這一點。就是這樣。

讓我們定義部分和B[x] = sum(i in (0, x+1), a[i])
的陣列B現在問題變爲找到索引q和w使得w<=q，q-w <=k，並B[q] - B[w]是可能的最大值。

要做到這一點，我們將通過陣列B到找出q。由於B[q]是固定的，因此當B[w]是最小值時，我們將最大化表達式。我們保留一個雙端隊列來快速找到w。德克將保持潛在最低點的位置。要更新它，請執行以下操作：取出第一個元素，因爲它在所需的k間隔之外，從後面提取所有值，使其大於當前位置的值，最後在當前位置插入當前位置。

應該是這樣的

for (q in len(b)) 
    // The minimum is too far behind 
    if !deque.empty() && q - deque.front() > k: deque.pop_front() 
    // Remove the less optimal positions from the queue. 
    while (!deque.empty() && b[deque.back()] > b[q]) deque.pop_back() 
    deque.push_back(q) 

    if (b[q] - b[deque.front()] > best_so_far) UpdateBestSoFar();

它可能看起來像，因爲在裏面的O（N^2），但事實並非如此。每個元素被插入到deque中一次，並提取一次。所以while迭代的總數是O（N）。

來源

2015-09-11 09:45:20 Sorin

我相信這是正確的，但它會幫助提的是你保持不變，在雙端隊列中所列位置對應於非降B []的值 - 這就是讓你有信心，'雙端隊列。front（）'總是一個最小生產位置，而不必搜索每個元素在deque中尋找最小的。 –

這太棒了！這與我的做法非常相似：我基本上正在修復w並尋找最佳q。要做到這一點，我保持一個堆，以便我可以快速獲得最大B [q]。這個答案不僅是正確的，但改善了我原來的解決方案。 –

你確定嗎？你怎麼能保持增加'B'的不變性？以op的例子來說，你將擁有'B == [0,8,7，6,10 ...]'。這聽起來不正確。 – HuStmpHrrr

回答

相關問題