<p>Given an integer array <code>arr</code>, partition the array into (contiguous) subarrays of length <strong>at most</strong> <code>k</code>. After partitioning, each subarray has their values changed to become the maximum value of that subarray.</p>

<p>Return <em>the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a <strong>32-bit</strong> integer.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,15,7,9,2,5,10], k = 3
<strong>Output:</strong> 84
<strong>Explanation:</strong> arr becomes [15,15,15,9,10,10,10]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
<strong>Output:</strong> 83
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [1], k = 1
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 500</code></li>
	<li><code>0 &lt;= arr[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= k &lt;= arr.length</code></li>
</ul>

# 隔数组以得到最大和

# 整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。
# 分隔完成后，每个子数组的中的所有值 -> 都会变为该子数组中的最大值。

# 返回将数组分隔变换后能够得到的元素最大和。
# 本题所用到的测试用例会确保答案是一个 32 位整数。

# 這題的目的是要將陣列 arr 分割成最長為 k 的子陣列，並將每個子陣列內的所有數字都改為該子陣列中的最大值，最後返回這樣操作後，所有數字的總和。
# 為了找到總和最大的分割方式，我們可以使用動態規劃來解決這個問題。

# 解題思路
# 我們使用一個動態規劃陣列 dp，其中 dp[i] 表示前 i 個元素的最大分割總和。
# 具體來說，我們遍歷每一個 i，並在每個位置嘗試將前面的最多 k 個元素作為一個子陣列來分割。
# 對於每一個可能的分割，我們計算子陣列的最大值並更新當前的 dp[i]。

# 詳細步驟
# 定義動態規劃陣列 dp，其中 dp[i] 表示前 i 個元素的最大分割總和，初始值為 0。
# 從左到右遍歷 arr，對於每一個位置 i，嘗試將從 i 開始的最多 k 個元素分割成一個子陣列，並將該子陣列中的所有元素都設為最大值。
# 對於每一個可能的分割子陣列，更新 dp[i] 為目前最大的總和。

# 動態規劃轉移方程
# 對於每一個位置 i，我們考慮從 i-j+1 到 i 這段區間內的數字（其中 j 的範圍是從 1 到 k 且 i-j+1 必須是合法的陣列範圍）。
# 找到該區間內的最大值 max_val，並更新 dp[i]：
# 其中 dp[i-j] 表示從 0 到 i-j 的最大總和，j * max_val 表示分割後的子陣列的總和。
# dp[i] = max(dp[i], (dp[i - j] if i >= j else 0) + max_val * j)

# 對每一個 i，嘗試從 i 往回最多 k 個元素形成子陣列，找到該子陣列的最大值，然後用此最大值更新 dp[i]。
# k 的區間 1 - k
# 對於每個 i , loop k 區間 j -> range(1, min(k, i + 1) + 1):
# 找區間內最大 element -> max_element

# arr[i - j + 1] -> i 到 j 間的位置, 包含i
# 要將當前位置 i 之前的 j 個數字分成一個子陣列，然後計算這個子陣列的最大值 max_val，再用該最大值來更新動態規劃陣列 dp[i]。
# i 是當前索引，表示我們現在要處理的最後一個元素。
# j 表示子陣列的長度，範圍是 1 到 k。
# 如果我們想取一個長度為 j 的子陣列，並且它的最後一個元素是 arr[i]，那麼這個子陣列的第一個元素應該是 arr[i - j + 1]。

# min(k, i + 1) -> 在每個位置 i，能夠往前劃分長度為 1 到 k 的子陣列
# 確保我們不會超出陣列邊界，並且正確地劃分子陣列的長度
# 當 i 比較小時，比如當 i < k 時，我們不可能劃分出長度為 k 的子陣列
# 當 i >= k 時，我們可以劃分長度為 k 的子陣列。
# 當 i < k 時，能劃分的子陣列最大長度為 i + 1，即最多只能從第 0 個元素到第 i 個元素，這是子陣列的最大範圍。
# i + 1 的含義是「從第 0 個元素到第 i 個元素，總共有 i + 1 個元素」。
# 如果 i = 0，代表這是第一個元素，我們可以形成的子陣列長度只能是 1，所以 i + 1 = 1。 
# 如果 i = 1，這時候從 arr[0] 到 arr[1] 的子陣列有 2 個元素，i + 1 = 2。 如果 i = 2，那麼從 arr[0] 到 arr[2] 的子陣列有 3 個元素，i + 1 = 3。

# 區間 window value -> max_element * j
# 區間 之前 value -> (dp[i - j] if i >= j else 0)
# dp[i] = max(dp[i], (dp[i - j] if i >= j else 0) + max_val * j)

# DP Bottom Up, math
# O(n * k), s:O(n)
class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0] * n  # dp[i] 表示前 i+1 個元素的最大分割總和
        
        for i in range(n):
            max_element = 0  # 當前子陣列的最大值
            for j in range(1, min(k, i + 1) + 1):
                max_element = max(max_element, arr[i - j + 1])  # 更新子陣列的最大值
                # 更新 dp[i]，考慮分割 i-j+1 到 i 的區間
                dp[i] = max(dp[i], (dp[i - j] if i >= j else 0) + max_element * j)
        
        return dp[-1]       
16500