※ 引述《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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1613627212.A.145.html