leetcode 1043. Partition Array for Maximum Sum （python）

「 This is my participation 11 The fourth of the yuegengwen challenge 19 God , Check out the activity details ：2021 One last more challenge 」

describe

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.

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]
 Copy code 

Example 2:

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

Example 3:

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

Note:

1 <= arr.length <= 500
0 <= arr[i] <= 10^9
1 <= k <= arr.length
 Copy code 

analysis

According to the meaning , Given an array of integers arr, Divide the array into several, with a length of at most k A continuous subarray of . After partition , The value of each subarray becomes the maximum value of the subarray . The title requires us to return the maximum possible sum of the new array after partitioning . The meaning of the question is very clear , Combined with example 1, we can fully understand the meaning of the question .

This question was written after reading the answer of the great God , Using a one-dimensional dynamic programming array solution , There is a link at the end of the text

• The initialization length is len(arr) One dimensional array of , dp[i] That means arr[:i] The maximum sum obtained after operation ,
• Traverse range(N) , That's traversal arr All element position indexes in i , Re traversal range(i,max(-1, i-k),-1) That is, the possible subarray location index j , Constantly update the maximum value of the current sub array MAX, And constantly updated dp[i] = max(dp[i], dp[j-1] + MAX*(i-j+1)) , Pay attention to the limitations of boundary conditions .
• Return after traversal dp[-1] Is the answer

answer

class Solution(object):
    def maxSumAfterPartitioning(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        N = len(arr)
        dp = [0 for _ in range(N)] 
        for i in range(N):
            MAX = 0
            for j in range(i,max(-1, i-k),-1):
                MAX = max(arr[j], MAX)
                if j>=1:
                    dp[i] = max(dp[i], dp[j-1] + MAX*(i-j+1))
                else:
                    dp[i] = max(dp[i], MAX*(i-j+1))
        return dp[-1]
                 
 Copy code 

Running results

Runtime: 408 ms, faster than 61.04% of Python online submissions for Partition Array for Maximum Sum.
Memory Usage: 13.4 MB, less than 94.81% of Python online submissions for Partition Array for Maximum Sum.
 Copy code 

Original link ：leetcode.com/problems/pa…

Explanation of the great God ：www.bilibili.com/video/BV143…

Your support is my greatest motivation