最大大小總和爲n

Question

現在的問題是從本地黑客馬拉松： 我有一個正序整數排序降序排列。例如（9,4,2,1）。您可以遍歷數組中的n個元素以最大化總和（最初n =數組的大小）。當你從頭到尾遍歷數組時，你可以隨時停下來再從頭開始，但是這樣做的代價是你從你的津貼中失去了一個元素。例如，在這種情況下，最好的方法是9,0,9,4。請注意，我已經停止了，失去了一個元素（因此爲0）並繼續。

我想用動態規劃解決這個問題。我知道如何在O（n^2）中使用DP來做到這一點。我正在尋找一種更好的時間複雜度的算法。

Answer 1

在重新啓動之間的某個其他時間間隔內，您不想在重新啓動和k + 2數字之間的某個時間間隔內取得k個數字;每次參加K + 1總是至少是一樣的。這意味着，鑑於重新啓動的次數，立即清楚該模式應該是什麼（儘可能均勻）。

在時間O（n）中，可以預先計算數組的每個前綴的總和。然後，在時間O（n）中，遍歷所有可能的重新啓動計數，通過檢查兩個相鄰前綴的總和並乘以每個相應的前綴的適當次數來計算每個時間的每個O（1）總和。