PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[心得] Maximum sum k-disjoint subarrays

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間8年前 (2016/03/04 09:22)推噓3(3推 0噓 4→)

留言7則, 3人參與討論串1/2 (看更多)

題目：給定一含有 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://www.ptt.cc/bbs/Prob_Solve/M.1457054558.A.D5F.html