“This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

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

Example 2:

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

Example 3:

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

Note:

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

parsing

Given an integer array arr, divide the array into contiguous subarrays of at most k length. After partitioning, the value of each subarray is changed to the maximum value of that subarray. They want us to return the largest possible sum of the new array after partitioning. The meaning of the question is very clear, combined with example 1 basic also can understand the meaning of the question completely.

This problem is to see the big god’s solution to write out, using the one-dimensional dynamic programming array solution, the end of the article has the big god pushed to the link

  • Initialize the one-dimensional array len(arr), dp[I] represents the maximum sum of arr[: I] after the operation,
  • Iterate over range(N), which is the index I of all elements in arR, iterate over range(I, Max (-1, i-k),-1), which is the possible index J of subarray positions, constantly updating the maximum value of the current subarray Max, Dp [I] = Max (dp[I], dp[J-1] + Max *(i-j+1));
  • At the end of traversal, return dp[-1] as 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 the code

The results

Each node in the given list has the same length of each node in the linked list. The linked list is given in the linked list.Copy the code

Original link: leetcode.com/problems/pa…

Great god explanation: www.bilibili.com/video/BV143…

Your support is my biggest motivation