※ 引述《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) 算法是可行的）