Algorithm--Partition-array-for-maximum-sum
Dynamic Programming
Partition Array for Maximum Sum
Title Detail
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:
1
2
3 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
2 1 <= K <= A.length <= 500
0 <= A[i] <= 10^6
思路
动态规划 问题。
用一个长度为
A.length
的数组dp
维护最终的加和结果。计算思想如下:
dp[i] := max sum of A[0] ~ A[i]
dp[i] = max{dp[i – k] + max(A[i+1-k:i]) * k}, 1 <= k <= min(i, K)
最终返回结果
dp[A.length-1]
Algorithm
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 孙云增的博客!
评论