<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>

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        # bottom up DP
        dp = [0] * k
        dp[0] = arr[0]

        for i in range(1, len(arr)):
            cur_max = 0
            max_at_i = 0
            for j in range(i, i - k, -1):
                if j < 0:
                    break
                cur_max = max(cur_max, arr[j])
                window_size = i - j + 1
                cur_sum = cur_max * window_size
                sub_sum = dp[(j - 1) % k] if j > 0 else dp[-1]
                max_at_i = max(max_at_i, cur_sum + sub_sum)

            dp[i % k] = max_at_i
        return dp[(len(arr) - 1) % k]

 
        # memoization
        cache = {}

        def dfs(i):
            if i >= len(arr):
                return 0
            if i in cache:
                return cache[i]

            cur_max = 0
            res = 0
            for j in range(i, min(i + k, len(arr))):
                cur_max = max(cur_max, arr[j])
                window_size = j - i + 1
                res = max(res, dfs(j + 1) + cur_max * window_size)
            cache[i] = res
            return cache[i]
 
        return dfs(0)
 
        # states
        # index, count
        # max_sofar, partial length
        # sum

        # choices:
        # if k > 0: end current subarray or not
        # if k == 0: forced to end

        dp = {}

        def dfs(i, count, max_sofar, parsum):
            if i == len(arr):
                return parsum

            if i in dp:
                return dp[i]

            # end subarray and update
            res = dfs(
                i + 1,
                k, -1,
                parsum + max(max_sofar, arr[i]) * (k - count + 1))

            # keep growing 
            if count > 0:
                res = max(
                    res, 
                    dfs(i + 1, count - 1, max(max_sofar, arr[i]), parsum)
                )

            dp[i] = res
            return dp[i]

        return dfs(0, k, -1, 0)
16900