[LeetCode] 1043. Partition Array for Maximum Sum

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

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Partition Array for Maximum Sum

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.

 

정수 배열 arr이 주어진다.

배열을 최대 k의 길이로 나눌 수 있다.

나누고 나서, 각 부분배열의 값들은 그 부분배열 내의 최대값이 된다.

이 부분배열들의 값들을 모두 더한 값을 반환하시오.

 

32비트정수 내로 범위가 설정되어있습니다.

 

풀이

dp[i] = i부터 시작하는 배열의 최대값

 

배열을 뒤부터 탐색하면서, 그룹의 범위를 정한다.

각 범위에서 최대의 숫자를 구하고, 

dp[start % (k+1)]에 dp[(i+1) % (k+1)] + 최대숫자 * i-start+1과 비교하여 최대값을 갱신시킨다.

dp[0]에는 최대값이 저장되어 있다.

 

코드

C++

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        const int n = arr.size();
        vector<int> dp(n+1, 0);

        for(int start = n-1; start >= 0; start--) {
            int maxVal = 0;
            int end = min(n, start+k);

            for(int i = start; i < end; i++) {
                maxVal = max(maxVal, arr[i]);
                dp[start % (k+1)] = max(dp[start % (k+1)], dp[(i+1) % (k+1)] + maxVal * (i-start+1));
            }
        }

        return dp[0];
    }
};