Partition Array for Maximum Sum

1043. Partition Array for Maximum Sum

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

i 위치가 i - 1 까지의 정답인 dp array 를 만든다.
max 의 1..k 곱 중 가장 큰 값을 뽑아 정해진 j 값 직접 값과 더하면 가장 큰 합이 된다.
max = max(arr[i - 1], arr[i - j])
dp[i] = max(dp[i - j] + max * j)

arr.size() == n

Time: O(n * k)

• dp 테이블 모두 순회하므로 n * 각 iteration 당 k 번의 최대값 구하므로 k

Space: O(n)

• dp 테이블 n