题目：给定一含有 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 个就是答案了。 感觉还是有点复杂，不知道有没有比较简单的想法。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 65.96.6.117 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1457054558.A.D5F.html ※ 编辑: FRAXIS (65.96.6.117), 03/05/2016 06:34:21