楼主:
FRAXIS (喔喔)
2016-03-04 09:22:23题目：给定一含有 n 个整数的阵列 A ，找出不相交的 k 个子阵列其总和最大。
也就是要找 k 组索引对 (b1, e1), ... (bk, ek), bi < ei 且 ei < b_{i+1}
使得 A[bi...ei] 的总和最大。
出处:
http://www.lintcode.com/en/problem/maximum-subarray-iii/
这问题理论上线性时间可解，可以参考 http://goo.gl/llwDs8 和
http://arxiv.org/pdf/1410.2847.pdf 但是方法有点复杂。
首先，我们可以把问题稍微简化一点，把所有为零的元素去掉，头尾的
负数去掉，然后把所有同号的子阵列合并为一个元素。
在不失一般性的情况下可以假设阵列中有多于 k 个正整数
所以我们可以假设下列性质
所有偶数的 i, A[i] 为正
所有奇数的 i, A[i] 为负 (阵列是从 0 起算)
A[0] 和 A[n-1] 皆为正 且 n > 2k - 1 。
因为是要算子阵列的总和，可以使用 prefix sum 的技巧。
令 P[i] = A[0..i] 的总和，那么 A[i..j] 的总和就可以用 P[j] - P[i - 1]
来求（假设 P[-1] = 0），又因为 A 阵列是正负交替出现的，
P 阵列会满足 对于所有偶数的 i, P[i-1] < P[i] > P[i+1] 如果 i-1, i+1 合法
所以这问题可以转换成以下问题
给定一含有 n 个整数的阵列 P ， P[i-1] < P[i] > P[i+1]
找出 k 组索引对 (b1, e1), ... (bk, ek), bi < ei 且 ei < b_{i+1}
使得 P[ei] - P[bi] 总和最大 (P[-1] = 0)
可以把 P[i] 当成股票在第 i 天的价格，允许作 k 次交易，求最大的获利。
出处:
http://codeforces.com/problemset/problem/391/F3
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
同样这题也是线性时间可解的
http://www.tachenov.name/2016/best-time-to-buy-and-sell-stock-iv/
https://maskray.me/blog/2015-03-27-leetcode-best-time-to-buy-and-sell-stock-iv
我觉得这个解法有点难懂，所以推敲了很久，以下是我思考的结果：
考虑两组不相交索引对 (b, e) 和 (b', e'), e < b'
其在 P 中相对应的值为 [l, h] 和 [l', h']
亦即 l = P[b], h = P[e], l' = P[b'] 和 h' = P[e'] (l代表低点, h 代表高点)
只考虑 l < h 和 l' < h' 的情况，因为买高卖低没意义。
如果 l >= l' ，那么我们不需要考虑 b 跟 e' 之后的索引配对的情况，因
为可以用 l' 来配对，所以我们可以忽略所有(b, e) 对 (b', e')之后的影响。
如果 l < l' ，那 l 就有可能会跟 e' 之后的索引配对，所以(b, e)要保留。
我们可以一个一个考虑索引对 (b, b+1) for b = -1, 1, ... n - 2
然后用一个 stack 来维护可跟之后元素结合的索引对。
此 stack 会满足一个单调性：
令 (b1, e1), ..., (bt, et) 为 stack 中的索引对(t为顶端)，这
些索引对必不相交，且 ei < b_{i+1}。
令 [l1, h1], ..., [lt, ht] 为索引在 P 中相对应的值，则必满足
[li, hi] 严格包含 [l_{i+1}, h_{i+1}] 如果把 [l, h] 想成区间
而维护这个性质也不难，当新进来一组索引对 (b, e)，其起点 b 必在所
有在 stack 中的索引对之后。令其对应的值为 [l = P[b], h = P[e]]
如果 lt >= l， 那么 stack 顶端的索引对以后不会需要了，把此索引对
从 stack 中移除，把 [lt, ht] 丢到一个 list L 里面，以备最后挑选。
重复此动作直到 lt < l 为止。
当 lt < l 时，有两种情况:
ht > h: 亦即 [l, h] 是被 [lt, ht] 包含的，那就把 [l, h] 放到 stack 里面。
ht <= h: 这情况比较麻烦，因为 [lt, ht] 和 [l, h] 没有包含关系。
此时我们可以假装把 [lt, ht] 和 [l, h] 合并为 [lt, h]。
因为 lt < l ，所有可以跟 l 配对的都不会比跟 lt 配对
来的好，所以并不会漏掉可以配对的情况。
但是这样作会漏掉把 [lt, ht] 和 [l, h] 分别选取的情况。
不过我们知道分别选择会得到
(ht - lt) + (h - l) = (h - lt) + (ht - l)
也就是说分别选择的话，可多得到 ht - l 。
所以如果 ht - l > 0 的话，我们可以把一个假的区间 [l, ht]
丢到 L 中，其值为(ht - l)，以备最后挑选。
重复此动作直到 ht > h。
当把所有索引对处理完之后，把 stack 中所有的索引对其相对应的值区间
都丢到 L 中，从 L 里面挑出值最大的 k 个就是答案了。
感觉还是有点复杂，不知道有没有比较简单的想法。