<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 {
public:
    int maxSumAfterPartitioning(vector<int>& nums, int k) {
        //return dfs(0, 0, 0, nums, k);
        // memset(dp, -1, sizeof(dp));
        //  dfs2(0, k, nums);
        //  return dfs2(0, k, nums);

        // vector<int> dpp(nums.size() + 1, 0);
        list<int> dpp = {0};
        int size = (int)nums.size();

        for (int idx = size - 1; ~idx; --idx) {
            int currMax = 0;
            int ans = 0;
            auto iter = dpp.begin();
            for (int it = idx; it < min(idx + k, size); ++it) {
                currMax = max(currMax, nums[it]);
                ans = max(ans, currMax * (it - idx + 1) + *iter++);
            }
            cout << ans << endl;
            if (dpp.size() == k) {
                dpp.pop_back();
            }
            dpp.emplace_front(ans);
        }
        return dpp.front();
    }
private:
// int dp[500];
//     long long dfs(int left, int right, long long sum, vector<int>& nums, int k) {//O(n^2)
//         if (right - left + 1 > k) {
//             return INT_MIN;
//         }
//         if (right == nums.size() && left == nums.size()) {
//             return 0;   
//         }
//         if (right == nums.size() || left == nums.size()) {
//             return INT_MIN;
//         }
//         sum = max(sum, (long long)nums[right]);
//         long long keepRange = dfs(left, right + 1, sum, nums, k);
//         long long newRange = dfs(right + 1, right + 1, 0, nums, k) + sum * (right - left + 1);    

//         return max(keepRange, newRange);
//     }
//     long long dfs2(int idx, int k, vector<int>&nums) {//O(n * k)
//         if (idx == nums.size()) {
//             return 0;
//         }
//         int currentMax = 0;
//         long long sum = 0;
//         if (~dp[idx]) {
//             return dp[idx];
//         }
//                 // 3 7 9 30 20 10 0
//         for (int i = idx; i < min(idx + k, (int)nums.size()); ++i) {
//             currentMax = max(currentMax, nums[i]);
//             long long x= dfs2(i + 1, k, nums);
//             sum = max(sum, currentMax * (i - idx + 1) + x);
//             printf("i %d idx %d next %d cuur %d\n",i, idx, x, sum);
//         }

//         return dp[idx] = sum;
//     }
};
static const auto init = [](){
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios_base::sync_with_stdio(false);

	return -1;
}();
11900