給定數組的一個子數組，它的值是它包含的出現奇數次的元素的最大值。我想將數組劃分為 K 個子數組以最大化子數組值的總和。例如，如果我們有以下數組5 6 6 3 9 且 K=2我們可以將其劃分如下：(5) + (6,6,3,9) = (5 + 9 => 14 )(5,6) + (6,3,9) = ( 6 +9 => 15 )(5,6,6) + (3,9) = ( 5 + 9 =>14 )(5,6,6,3) + (9) = ( 5 + 9 => 14 )我能夠以粗暴的方式做到這一點，但正在尋找一種有效的算法。你能提出一些建議嗎
3 回答
搖曳的薔薇
TA貢獻1793條經驗 獲得超6個贊
顯然，我們可以有O(n^2 * k)，因為如果f(i, k)代表可達到的最大可達A[i]用k零件，則：
f(i, k) = max(
// include A[i] in previous part
g(A[j..i]) + f(j - 1, k - 1),
// don't include A[i] in previous part
A[i] + f(i - 1, k - 1)
)
for all k <= j < i
where g(subarray) is the max element
in subarray that appears an odd number
of times
問題是我們如何更有效地選擇要測試的子數組A[i]。
添加回答
舉報
0/150
提交
取消