※ 引述《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