Leetcode 1043. Partition Array for Maximum Sum

문제

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.

1. 먼저 주어진 배열을 최대 k개의 길이를 가지는 subarray 로 쪼갭니다.
2. 이후 arr의 값은 자신이 해당한 subarray의 최댓값으로 했을때, 새로 계산된 arr의 합의 최댓값을 리턴하세요

예시

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr은 [15,15,15,9,10,10,10] 가 된다.
[[1, 15, 7], [9], [2, 5, 10]] 으로 나누어진다.

제한

• $1 <= arr.length <= 500$
• $0 <= arr[i] <= 10^9$
• $1 <= k <= arr.length$

풀이법

• subarray로 쪼개는것에서 알수 있듯, dp를 사용하며, 아이템을 순회하며 각 아이템별로 앞전의 subarray에 포함될지 새로운 subarray
  에 포함될지를 결정하게 한다.
• 만약 subarray의 크기가 이미 최대면 새로운 subarray를 만들수만 있어야 하며, arr을 최대값으로 바꾸는것은 subarray 내의 최댓값을 계속 추적하다 새로운 subarray를 만들면 기존 subarray 길이 * 최댓값만큼 더하면 된다.

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = {}
        def search(index: int, maximum: int, count: int) -> int:
        	// 끝에 도달했을때, 이미 만들어진 subarray들의 합.
            if index == len(arr):
                return maximum * count

		
            if (index, maximum, count) in dp:
                return dp[(index, maximum, count)]
            
            // 이미 길이가 k인 경우와 아닌 경우 둘로 나누어 dp를 계산해야 한다.
            if count == k:
                res = maximum * count + search(index + 1, arr[index], 1)
            else:
                res = max(
                    maximum * count + search(index + 1, arr[index], 1),
                    search(index + 1, max(arr[index], maximum), count + 1)
                )

            dp[(index, maximum, count)] = res

            return res