1
class Solution {
2
 public:
3
  int get_max(vector<int> &arr, int s, int e) {
4
    int mx_val = *max_element(arr.begin() + s, arr.begin() + e + 1);
5
    return (e - s + 1) * mx_val;
6
  }
7

8
  int solve(vector<int> &arr, int idx, int k, vector<vector<int>> &dp) {
9
    if (idx >= arr.size()) return 0;
10

11
    if (dp[idx][k] != -1) return dp[idx][k];
12

13
    int ans = 0;
14

15
    for (int i = 0; i < k; ++i) {
16
      if ((idx + i) > arr.size() - 1) break;
17

18
      int val = get_max(arr, idx, idx + i) + solve(arr, idx + i + 1, k, dp);
19
      ans = max(ans, val);
20
    }
21
    return dp[idx][k] = ans;
22
  }
23

24
  int maxSumAfterPartitioning(vector<int> &arr, int k) {
25
    vector<vector<int>> dp(arr.size() + 1, vector<int>(k + 1, -1));
26

27
    return solve(arr, 0, k, dp);
28
  }
29
};