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

description

Given an integer array arr, you should 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.

Example:

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]

Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83

Input: arr = [1], k = 1
Output: 1

Constraints

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 109
• 1 <= k <= arr.length

작성한 코드

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        length = len(arr)
        dp = [0] * length
        maxNum = arr[0]
        
        for i in range(k) :
            maxNum = max(maxNum, arr[i])
            dp[i] = maxNum * (i+1)

        for i in range(k,length):
            sub = arr[i]
            for size in range(1, k+1):
                sub = max(sub, arr[i-size+1])
                dp[i] = max(dp[i], dp[i-size]+sub*size)
 
        return dp[length-1]

설명

테스트케이스를 넣어보면서 이해해보자.

arr : [1,4,1,5,7,3,6,1,9,9,3]
k : 4

여기서 0~k-1 까지 순회하는 for문을 돌고나면 아래와 같다.

print(dp)
#  [1, 8, 12, 20, 0, 0, 0, 0, 0, 0, 0]

DP를 사용할 때는 초기 값들을 넣어주는데 이 for loop가 그 역할을 한다. 다음 for loop의 역할은 dp의 값을 결정한다. 현재 숫자를 k보다 작거나 같은 size만큼 갖는게 큰지, 아니면 이전의 dp가 더 큰지 max를 취하게 된다. 예를 들어 size for 문에서 dp를 찍어보면 아래와 같다.

for size in range(1, k+1):
    sub = max(sub, arr[i-size+1])
    dp[i] = max(dp[i], dp[i-size]+sub*size)
    print('dp', dp)

# dp [1, 8, 12, 20, 27, 0, 0, 0, 0, 0, 0]
# dp [1, 8, 12, 20, 27, 0, 0, 0, 0, 0, 0]
# dp [1, 8, 12, 20, 29, 0, 0, 0, 0, 0, 0]
# dp [1, 8, 12, 20, 29, 0, 0, 0, 0, 0, 0]

• 7을 2개 가질 때 vs. 7을 1개 가질 때
• 7을 3개 가질 때 vs. 이전의 dp
• 7을 4개 가질 때 vs. 이전의 dp

여기서 dp[i]는 arr[i]까지의 배열이 있을 때의 맥시멈 결과값이다.

이런 식으로 이중 for문을 돌고나면 dp [1, 8, 12, 20, 29, 36, 42, 48, 65, 74, 83] 를 갖게 된다. 결국 우리가 원하는 값은 arr[-1] 이므로 해당 값을 리턴한다.