題目：給定一含有 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 個就是答案了。
感覺還是有點複雜，不知道有沒有比較簡單的想法。