[leetcode] 1043. Partition Array for Maximum Sum

Description

Given an integer array arr, you should 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.

Example 1:

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]
           

Example 2:

Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
           

Example 3:

Input: arr = [1], k = 1
Output: 1
           

Constraints:

1. 1 <= arr.length <= 500
2. 0 <= arr[i] <= 109
3. 1 <= k <= arr.length

分析

题目的意思是：给你一个数组，划分成子数组，每个子数组的长度不超过k，数组中的每个值变成最大值，求分隔数组得到的最大和。

这道题用动态规划来解决，dp[i]表示前i个元素被分成Y刀了之后得到的最大值，比如是从位置j开始切割的,递推公式为：

dp[i]=max(dp[i],dp[j]+(i-j)*max_val) 
i-j<=k
           

现在是怎么知道max_val即最大值呢，可以从第i个位置往前遍历，用一个值t维护最大值就行了。哈哈挺难想到的，如果想到这个写出代码就很容易了。

代码

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n=len(arr)
        dp=[0]*(n+1)
        for i in range(n+1):
            j=i-1
            t=0
            while(i-j<=k and j>=0):
                t=max(t,arr[j])
                dp[i]=max(dp[i],dp[j]+(i-j)*t)
                j-=1
        return dp[n]
           

参考文献

[LeetCode] 动态规划解分割数组II[Arctic Fox]