99클럽 코테 스터디 20일차 TIL + Array/Dynamic Programming : partition-array-for-maximum-sum

문제

링크텍스트

풀이

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        max_sum_after_here = [0]*(n+1)
    
        for i0 in range(n - 1, -1, -1):
            max_i = 0
            i1 = min(n, i0 + k)

            for i in range(i0, i1):
                max_i = max(max_i, arr[i])
                max_sum_after_here[i0] = max(max_sum_after_here[i0], max_sum_after_here[i + 1] + max_i * (i - i0 + 1))
                
        return max_sum_after_here[0]

• 최대값으로 변환된 개별 subarray 모두의 총합이 최대가 되려면, 큰 수가 포함된 subarray의 길이가 가능한 한 크게 되도록 partition 해야 합니다.
• 처음에는 재귀함수를 사용하였으나 앞에서부터 최종결과를 얻을 때까지 중간 결과를 계속 쌓아 두기 때문에 시간이 오래 걸렸습니다.
• 결국, 맨 뒤에서부터 subarray의 크기를 1에서 최대 k까지 바꾸어 가면서 최대가 되도록 하였습니다.

결과