[99클럽] 19일차 TIL

leetcode 문제를 풀어 보았습니다.

 

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

 

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n + 1)


        for i in range(1, n + 1):
            max_val = float('-inf')


            for j in range(1, min(i, k) + 1):
                max_val = max(max_val, arr[i - j])


                dp[i] = max(dp[i], dp[i - j] + max_val * j)
                
        return dp[n]

 

동적계획법은 아직도 너무 어렵다..