PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [心得] Maximum sum k-disjoint subarrays

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間3年前 (2021/02/18 13:46)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《FRAXIS (喔喔)》之銘言： : 題目：給定一含有 n 個整數的陣列 A ，找出不相交的 k 個子陣列其總和最大。 : 也就是要找 k 組索引對 (b1, e1), ... (bk, ek), bi < ei 且 ei < b_{i+1} : 使得 A[bi...ei] 的總和最大。最近有人跟我說這一題有另一種想法，所以跟大家分享一下。可以參考這個網站： http://www.serbanology.com/article/The%20Trick%20From%20Aliens 解題的技巧叫做 Alien's Trick (IOI 2016 的 Aliens 題）或是 WQS binary search。簡單來說，如果 A 是給定，我們令 f(x) 為不相交 x 個子陣列最大的總和（此時 x 是變量，雖然我們只想算 f(k)）。然後引入 Lagrange multiplier λ，計算 L(x, λ) = f(x) - λx。可以想像 λ 是建立一個新子陣列的 penalty 。（我其實看不太出來這跟 Lagrange multiplier 有甚麼關係，雖然函數很像，但是 Lagrange multiplier 主要是在處理連續的函數而不是離散函數）此時我們會發現 λ 增加時，argmin_x L(x, λ) 會減少。當 λ 是 0 時，因為建立子陣列的 penalty = 0，就是挑 A 中所有的正數，每一個正數是一個獨立的子陣列。當 λ 很大時，就會挑比較少子陣列。想法就是 binary search λ，直到 argmin_x L(x, λ) = k 為止，而 argmin_x L(x, λ) 可以用 DP 在線性時間內算出。 λ 一般都可以找出合理的上限 U，所以不會時間複雜度可以是 O(n lg U)。（真要分析的話，只需要考慮 λ = A[i..j] 總和的情況，因為 i, j 只有 O(n^2) 組合，而且可以藉由建構 prefix sum array 的方式計算子陣列總和，所以應該 O(n lg n) 算法是可行的） -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.202.90.47 (美國) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1613627212.A.145.html