1043.md

1043. Partition Array for Maximum Sum

Solution 1 (time O(nk), space O(n))

# Dynamic programming
class Solution(object):
    def maxSumAfterPartitioning(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        n = len(arr)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            max_val = -float("inf")
            for j in range(i - 1, max(-1, i - k - 1), -1):
                max_val = max(max_val, arr[j])
                dp[i] = max(dp[i], dp[j] + max_val * (i - j))
        return dp[-1]