<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:
        best_arr_sums = {}
        n = len(arr)
        dfs_stack = [(n, False)]
        while dfs_stack:
            node, visited = dfs_stack.pop()
            if node <= k:
                best_arr_sums[node] = (node * max(arr[:node]), [node])
            if node > k:
                if visited:
                    best_sum = best_arr_sums[node-1][0] + arr[node-1]
                    best_partition = best_arr_sums[node-1][1].copy()
                    best_partition.append(1)
                    for i in range(1, k+1):
                        new_sum = best_arr_sums[node-i][0] + i*max(arr[node-i:node])
                        new_partition = best_arr_sums[node-i][1].copy()
                        new_partition.append(i)

                        if new_sum > best_sum:
                            best_sum = new_sum
                            best_partition = new_partition.copy()
                    best_arr_sums[node] = (best_sum, best_partition.copy())
                else:
                    dfs_stack.append((node, True))
                    for i in range(1, k+1):
                        if (node - i) not in best_arr_sums:
                            dfs_stack.append((node-i, False))
        
        return best_arr_sums[n][0]
17900