leetcode 1043. Partition Array for Maximum Sum （python）_王大呀呀

leetcode 1043. Partition Array for Maximum Sum （python）

語言: CN / TW / HK

「這是我參與11月更文挑戰的第19天，活動詳情檢視：2021最後一次更文挑戰」

描述

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]

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

Note:

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

解析

根據題意，給定一個整數陣列 arr，將該陣列劃分為幾個長度至多為 k 的連續子陣列。分割槽後，每個子陣列的值都變為該子陣列的最大值。題目要求我們分割槽後返回新陣列可能的最大和。題意很清楚，結合例子一基本也就能完全理解題意了。

這道題是看了大神的解答才寫出來的，使用的是一維動態規劃陣列解答，文尾有大神推到連結

初始化長度為 len(arr) 的一維陣列， dp[i] 表示的就是 arr[:i] 經過操作後得到的最大和值，
遍歷 range(N) ，也就是遍歷 arr 中的所有元素位置索引 i ，再遍歷 range(i,max(-1, i-k),-1) 也就是可能的子陣列位置索引 j ，不斷更新當前子陣列的最大值 MAX，又不斷更新 dp[i] = max(dp[i], dp[j-1] + MAX*(i-j+1)) ，注意邊界條件的限制。
遍歷結束返回 dp[-1] 即為答案

解答

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]

執行結果

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.

原題連結：http://leetcode.com/problems/partition-array-for-maximum-sum/

大神解釋：http://www.bilibili.com/video/BV143411z7ek

您的支援是我最大的動力