1043. Partition Array for Maximum Sum.cpp

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int K) {
        int N = arr.size();
        vector<int> dp(N + 1);
        for (int i = 1; i <= N; ++i) {
            int curMax = 0, best = 0;
            for (int k = 1; k <= K && i - k >= 0; ++k) {
                curMax = max(curMax, arr[i - k]);
                best = max(best, dp[i - k] + curMax * k);
            }
            dp[i] = best; 
        }
        return dp[N];
    }
};