Leetcode 1121 Solution

This article provides solution to leetcode question 1121 (partition-array-for-maximum-sum)
Categories:
Tags:
Access this page by simply typing in "lcs 1121" in your browser address bar if you have bunnylol configured.

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

Solution

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

        for i in range(len(A)):
            prev_sum = dp[i - 1] if i > 0 else 0
            cur_max = 0
            for k in range(K):
                if i + k >= len(A):
                    break
                cur_max = max(cur_max, A[i + k])
                dp[i + k] = max(dp[i + k], prev_sum + cur_max * (k + 1))

        return dp[-1]