[LeetCode] 1043 Partition Array for Maximum Sum

💡  오늘의 학습 키워드

📌  동적 프로그래밍

 

문제 설명

문제 링크 : https://leetcode.com/problems/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. 1 <= arr.length <= 500
2. 0 <= arr[i] <= 10^9
3. 1 <= k <= arr.length

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

 

💡 내가 해결한 방식은?

동적 프로그래밍을 사용한 풀이 (280ms)

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

        for i in range(len(arr)):
            max_val = 0
            for j in range(1, min(k, i+1)+1):
                max_val = max(max_val, arr[i-j+1])
                if i >= j:
                    dp[i] = max(dp[i], dp[i-j] + max_val * j)
                else:
                    dp[i] = max(dp[i], max_val * j)

        return dp[-1]

 

---

✍️  TIL