找到一組數組中最高總和的算法

Question

我的問題是：我需要一個算法，如果我有一些列表，按照特定的順序，我想找到一組值給我最高的總和。事實是，當我拿出一個價值時，它必須大於或等於最後一次採取的價值。舉個例子：

• 列表1 {5, 10, 1}

• 列表2 {9, 8}

• 項目list3 {4, 4, 4, 4, 4}

正確的答案是{1, 5, 8, 9}

（其實我在第一個列表中取1和5，然後丟棄10，因爲如果我拿它，我不能取9和8，哪個總和大於10.我丟棄4,4,4,4,4，因爲如果我拿他們，我會放棄其他陣列中1和4之間的所有數字）。

我希望我能讓自己清楚。感謝您的幫助。

Answer 1

你可以用最長的增加的子序列算法的變化來解決這個問題。 LIS存儲迄今爲止發現的最佳長度，而您需要的算法將存儲迄今爲止採用的項目總和。在運行結束時，存儲在輔助數組中的最高總和將爲您的問題提供答案。