目錄
今天(2/3)的 Daily 是難度為 medium 的 1043. Partition Array for Maximum Sum。
題目分析
題目
Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.
給你一個整數數組arr，請你將該數組分隔為長度最多為k 的一些（連續）子數組。分隔完成後，每個子數組的中的所有值都會變成該子數組中的最大值。
Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.
傳回將陣列分隔變換後能夠得到的元素最大和。本題所用到的測試案例會確保答案是一個32 位元整數。
Example 1:
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]
Example 2:
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
Example 3:
Input: arr = [1], k = 1
Output: 1
Constraints:
1 <= arr.length <= 500
0 <= arr[i] <= 109
1 <= k <= arr.length
分析
題目的操作很簡單：
-
將數列拆分為由相鄰的幾個數組成的分組，各分組長度需介於[1,k]
-
各分組的數全部改為組內最大者
-
求所有分組方法中，最大的總和
能貪心嗎？
經過簡單思考後可知，對於整個數列中最大的數，例如Example 1.中最大的「15」，必定是希望他能夠分進擁有最多數字的組別，也就是例題所指定的 k=3，如此一來，就能使最多的數把自己的值修改為最大的15。依此類推，接下來最大的10也會希望能夠分到三個數一組。
這是一個 貪心算法(Greedy) 的思維，不過在這題貪心算法能work嗎？
進一步思考之後，會發現這是不行的。原因如下：(繼續以Example 1.為例)
雖然我們已知道15這個數要分進3個數的組別，但是要和哪些數分組，是存在多種選項的：
1,[15,7,9],2,5,10
[1,15,7],9,2,5,10
這便超出了貪心算法能考量的範圍。每個數要分到哪一組才有最佳解，實際上會受到周圍的數的分布影響。換言之：
周圍的局部最佳解 → 求解 → 局部最佳解 → 求解 → 全局最佳解
也就是說，這題較適合使用動態規畫法求解，貪心算法並不適用。
筆者的心得是，儘管貪心算法在多數難題並不適用，在思考解題流程時仍然會將其放進視野。主要原因有兩個：
-
貪心算法的時間複雜度通常優於動態規劃等更複雜的作法。如果一個題目能使用貪心算法，通常會是僅次於「數學公式算法」的最佳解
-
思考貪心算法的過程中，往往能一併得出求局部最佳解的途徑。例如本題我們就在思考貪心算法的過程中，發現局部最佳解須從周邊的局部最佳解來推得。
換言之，能用貪心法時，就進入貪心法的求解，不能用時，其實也已經得出動態規劃法的藍圖，並沒有浪費多少時間。
動態規劃法 觀察
要應用DP求解，需要兩個資訊：
-
最小的局部最佳解 (base case)
-
如何從較小的局部解，推知較大的局部解 (recursive / iterative case)
繼續以Example 1.為例，本題的「最小局部解」，可以思考一個 長度<=k 的局部陣列：
1
1 15
1 15 7
依據題目，最多可以將 k=3 個數綁一組，並且改值為組間的最大值，所以這三組的局部最佳解，可以直接將所有數改為組內最大的數：
1
15 15
15 15 15
接著我們思考「如何從最小局部解，推到較大的局部解」
以這個 長度為4 的數列為例
1 15 7 9
因為題目的 k=3 ，必定需要分組。此時，考慮 9 應該和誰分組，可知有三種分法：
[1 15 7] [9]
[1 15] [7 9]
[1] [15 7 9]
可以發現，無論是哪一種分組方法，左邊的一組都已經在「最小局部解」求過最佳解了：
[15 15 15] [9]
[15 15] [7 9]
[1] [15 7 9]
接著，將右邊的一組求組間最大值，並將組內的數都改為組間最大值：
[15 15 15] [9]
[15 15] [9 9]
[1] [15 15 15]
分別計算三種方案的總和
[15 15 15] [9] = 54
[15 15] [9 9] = 48
[1] [15 15 15] = 46
可知第一種方案，即為此數列的最佳解。
動態規劃法 一般化
接著要做的分析稱為「一般化」，將前述我們找出來的解法，以數學式表示。
在這邊我們引入數列的 index i 幫助表示每個數的位置 (從0開始)
並且以 res(i) 表示 [0,i] 範圍子陣列 的局部最佳解
繼續以前述範例為例，探討前四像的局部最佳解：
1 15 7 9 原陣列值
0 1 2 3 index
三種方案：
[1 15 7] [9] 使用 前三項(i=0~2)的最佳解
[1 15] [7 9] 使用 前兩項(i=0~1)的最佳解
[1] [15 7 9] 使用 第一項(i=0) 的最佳解
也就是：
solve(2) + [9]
solve(1) + [7 9]
solve(0) + [15 7 9]
計算右邊組別的最大值，並求和
solve(2) + 1 x max([9])
solve(1) + 2 x max([7 9])
solve(0) + 3 x max([15 7 9])
以index表示右邊的組別 (Python語法)
solve(2) + 1 x max(arr[3:4])
solve(1) + 2 x max(arr[2:4])
solve(0) + 3 x max(arr[1:4])
以i=3 k=3 代換所有數字
solve(i-k+2) + (k-2) x max(arr[i+1-k+2:i+1])
solve(i-k+1) + (k-1) x max(arr[i+1-k+1:i+1])
solve(i-k) + k x max(arr[i+1-k :i+1])
以迴圈迭代
令 j 從 1 ~ k
solve(i-j) + (j) x max( arr[ i+1-j : i+1 ] )
求最大值，即為 solve(i)
至此，動態規劃所需的分析就大致完成了
解題思路
方案一、Top-down Dynamical programming
在前段的分析，我們找出了base case和recursive case的一般式：
-
base case
if i<k: solve(i) = max(arr[:i+1])*(i+1) -
recursive case
solve(i) = max( solve(i-j)+ j*max(arr[i+1-j:i+1]) for j in range(1,k+1) )這邊使用了Python的列表生成式，邏輯拆解開來是：
對j做for迴圈
計算每項的「 solve(i-j)+ j*max(arr[i+1-j:i+1]) 」值
再求其最大值
撰寫 Top-down Dynamical programming 的流程很簡單：
-
將前述的兩種case寫進遞迴函式
-
遞迴函式加上 @cache 修飾
(cache函式庫於同樣的 i 會自動以 hashmap 記錄答案，就不需重複計算)
-
執行遞迴函式
-
輸出結果
範例解答如下
class Solution:
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
@cache
def solve(i):
# base case
if i<k: return max(arr[:i+1])*(i+1)
# recursive case
return max(
solve(i-j)+ j*max(arr[i+1-j:i+1]) for j in range(1,k+1)
)
return solve(len(arr)-1)
方案二、Top-down Dynamical programming 優化
前面撰寫的Top-down DP隱含了一個效能問題：
我們不斷地重複計算 max(arr[i+1-j:i+1])
-
對所有的i僅呼叫一次solve(i)
(重複呼叫時，cache函示庫使用hashmap紀錄好的答案，以空間換取時間，不增加時間複雜度)
-
在solve(i)中，執行for迴圈，一共執行k次
-
在每層迴圈中，計算一次 max(arr[i+1-j:i+1])
由於一組的長度最長可為k，這個單一操作的最差時間複雜度(big-O) 為 O(k)
也就是說最終時間複雜度為 O(n k^2)
有沒有可優化的地方？
觀察發現，這個 max(arr[i+1-j:i+1])重複計算的問題可以被優化。
因為這個子陣列隨著j從0~k 會越來越長
只需要記錄當下的子陣列最大值，並且跟下一個遇到的值做比較，即可知下一個子陣列的最大值，而不需要重複比對整個子陣列。
以 Example 1.的前四項為舉例來說：
[15 15 15] [9] 目前右邊子陣列的最大值 = 9
[15 15] [7 9] 目前右邊子陣列的最大值(比較7 與9) = 9
[1] [15 7 9] 目前右邊子陣列的最大值(比較15與9) = 15
因此，創建一個變數 curMax 來記錄當前的子陣列最大值，並在迴圈的過程跟新加入的數比較，持續更新這個 curMax 來取代原本的 max(arr[i+1-j:i+1])
範例解答如下：
class Solution:
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
@cache
def solve(i):
# base case
if i<k: return max(arr[:i+1])*(i+1)
# recursive case
maxSum, curMax = 0, 0
for j in range(1,k+1):
curMax = max( arr[i+1-j] , curMax )
maxSum = max( solve(i-j)+ j*curMax , maxSum )
return maxSum
return solve(len(arr)-1)
方案三、Bottom-up Dynamical programming
跟Top-down的做法類似，Bottom-up 以一個list來記錄計算過的局部解，並且規劃計算順序從i=0開始計算。整個流程如下：
-
計算base case並填入記錄用的list
-
計算 iterative case (相當於 Top-down 時的 recursive case )，
並將結果填入記錄用的list
-
返回全局最佳解，以本題為例是 dp[i = len(arr) -1] 即 dp[-1]
範例解答：
class Solution:
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
dp = [0]*len(arr)
curMax = arr[0]
for i in range(k): # base case
curMax = max(arr[i], curMax)
dp[i] = curMax * (i+1)
for i in range(k,len(arr)): # iterative case
curMax, maxSum = 0, 0
for j in range(1,k+1):
curMax = max( arr[i+1-j] , curMax )
maxSum = max( dp[i-j]+ j*curMax , maxSum )
dp[i] = maxSum
return dp[-1]
複雜度分析
方案一 Top-Down DP(未優化)： T = O(n・k^2) S = O(n)
-
對所有的i僅呼叫一次solve(i)
(重複呼叫時，cache函示庫使用hashmap紀錄好的答案，以空間換取時間，不增加時間複雜度)
-
在solve(i)中，執行for迴圈，一共執行k次
-
在每層迴圈中，計算一次 max(arr[i+1-j:i+1])
由於一組的長度最長可為k，這個單一操作的最差時間複雜度(big-O) 為 O(k)
-
-
也就是說最終時間複雜度為 O(n k^2)
若忽略在每一層recursive stack中使用的空間資源，@cache對於所有的solve(i)儲存其「局部最佳解」，因此空間複雜度為 O(n)
方案二 Top-Down DP： T = O(n・k) S = O(n)
省掉了max函式那一層，時間複雜度簡化為 O(n・k)
空間複雜度不變。
方案三 Bottom-Up DP： T = O(n・k) S = O(n)
- 對每個index = i，計算一次
- 每次計算中，考慮k種分組情形中的最佳解
因此時間複雜度為 O(n・k)
使用1-D list 將每個 i 的計算結果(局部解)儲存起來，故空間複雜度為 O(n)
Leetcode 效能結果
結語
以DP設計的難度來說，算是普通的medium難度。
在優化的過程中發現，只要規劃一個好的計算順序，便可以優化「重複取區間最大值」的效能陷阱。
從本題的測資，可能會認為這個優化影響不大(1 <= arr.length <= 500)，但假如給定的陣列更大(例如當 n = 2x10^4 , k = 10^4 )，是否對區間max的求法優化便會產生巨大的效能差異。
感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！