leetcode

0 class Solution {

1 int dp[501];

2

3 public:

4 Solution() { memset(dp, 0xFF, sizeof(dp)); }

5 int maxSumAfterPartitioning(const vector<int> &arr, const int k, int idx = 0) {

6 if (idx == arr.size()) return 0;

7 if (dp[idx] != -1) return dp[idx];

8

9 int maxi = arr[idx];

10 int res = maxi + maxSumAfterPartitioning(arr, k, idx + 1);

11 for (int i = idx + 1; i < idx + k && i < arr.size(); i++) {

12 maxi = max(maxi, arr[i]);

13 res = max(res, (i - idx + 1) * maxi + maxSumAfterPartitioning(arr, k, i + 1));

14 }

15

16 return dp[idx] = res;

17 }

18 };