[LeetCode] 1043. Partition Array for Maximum Sum

https://leetcode.com/problems/partition-array-for-maximum-sum/

Partition Array for Maximum Sum - LeetCode

Partition Array for Maximum Sum

 

 

전체 풀이 코드

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