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 <= K <= A.length <= 500
0 <= A[i] <= 10^6
Solution: DP
Time complexity: O(n*k)
Space complexity: O(n)
dp[i] := max sum of A[1] ~ A[i]
init: dp[0] = 0
transition: dp[i] = max{dp[i – k] + max(A[i-k:i]) * k}, 1 <= k <= min(i, K)
ans: dp[n]
A = | 2 | 1 | 4 | 3 | K = 3 dp[0] = 0 dp[1] = max(dp[0] + 2 * 1) = 2 dp[2] = max(dp[0] + 2 * 2, dp[1] + 1 * 1) = max(4, 3) = 4 dp[3] = max(dp[0] + 4 * 3, dp[1] + 4 * 2, dp[2] + 4 * 1) = max(12, 10, 8) = 12 dp[4] = max(dp[1] + 4 * 3, dp[2] + 4 * 2, dp[3] + 3 * 1) = max(14, 12, 15) = 15 best = | 4 | 4 | 4 | 3 |
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: int maxSumAfterPartitioning(vector<int>& A, int K) { int n = A.size(); vector<int> dp(n + 1, 0); for (int i = 1; i <= n; ++i) { int m = INT_MIN; for (int k = 1; k <= K && i - k >= 0; ++k) { m = max(m, A[i - k]); dp[i] = max(dp[i], dp[i - k] + m * k); } } return dp[n]; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment