【leetcode】1043. Partition Array for Maximum Sum

雨点打透心脏的1/2处 2022-01-10 06:13 180阅读 0赞

**题目如下：**

> Given an integer array `A`, you 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: A = [1,15,7,9,2,5,10], K = 3 Output: 84 Explanation: A becomes [15,15,15,9,10,10,10]
> 
>  
> 
> Note:
> 
> 1.  `1 <= K <= A.length <= 500`
> 2.  `0 <= A[i] <= 10^6`

**解题思路：**假设dp\[i\]\[j\] 表示第i个元素为第j个子数组的最后一个元素时，A\[0:i\]可以获得的最大值。那么有dp\[i\]\[j\] = max(dp\[i\]\[j\], dp\[m\]\[j-1\] + max\_val\[m+1\]\[i\] \* (i-m))   ( i-k < m < i) 。

**代码如下：**

class Solution(object):
        def maxSumAfterPartitioning(self, A, K):
            """
            :type A: List[int]
            :type K: int
            :rtype: int
            """
            import math
            dp = []
            max_val = []
            sub = int(math.ceil(float(len(A))/K))
            for i in A:
                dp.append([0] * sub)
                max_val.append([0]*len(A))
            for i in range(len(A)):
                max_val[i][i] = A[i]
                for j in range(i+1,len(A)):
                    max_val[i][j] = max(max_val[i][j-1],A[j])
            dp[0][0] = A[0]
            for i in range(len(A)):
                for j in range(sub):
                    #print i,j
                    if i-K< 0:
                        dp[i][j] = max(A[0:i+1]) * (i+1)
                    else:
                        for m in range(i-K,i):
                            dp[i][j] = max(dp[i][j], dp[m][j-1] + max_val[m+1][i] * (i-m))
            #print dp
            return dp[-1][-1]

转载于:https://www.cnblogs.com/seyjs/p/11044749.html