Leetcode 1121 Solution

This article provides solution to leetcode question 1121 (partition-array-for-maximum-sum)

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]