Formatted question description: https://leetcode.ca/all/1043.html
1043. Partition Array for Maximum Sum (Medium)
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
Related Topics:
Graph
Solution 1. DP
Let dp[i]
be the subproblem in A[0..i]
.
dp[i] = max( dp[j-1] + max(A[j], ..., A[i]) * (i - j + 1) | i - j + 1 <= K && j >= 0 )
dp[-1] = 0
// OJ: https://leetcode.com/problems/partition-array-for-maximum-sum/
// Time: O(NK)
// Space: O(N)
class Solution {
public:
int maxSumAfterPartitioning(vector<int>& A, int K) {
int N = A.size();
vector<int> dp(N);
for (int i = 0; i < N; ++i) {
int maxVal = 0;
for (int j = i, k = 0; j >= 0 && k < K; --j, ++k) {
maxVal = max(maxVal, A[j]);
dp[i] = max(dp[i], (j == 0 ? 0 : dp[j - 1]) + maxVal * (i - j + 1));
}
}
return dp[N - 1];
}
};
Solution 2. DP
// OJ: https://leetcode.com/problems/partition-array-for-maximum-sum/
// Time: O(NK)
// Space: O(K)
class Solution {
public:
int maxSumAfterPartitioning(vector<int>& A, int K) {
int N = A.size();
++K;
vector<int> dp(K);
for (int i = 0; i < N; ++i) {
int maxVal = 0;
dp[i % K] = 0;
for (int j = i, k = 0; j >= 0 && k < K - 1; --j, ++k) {
maxVal = max(maxVal, A[j]);
dp[i % K] = max(dp[i % K], (j == 0 ? 0 : dp[(j - 1) % K]) + maxVal * (i - j + 1));
}
}
return dp[(N - 1) % K];
}
};
Java
-
class Solution { public int maxSumAfterPartitioning(int[] A, int K) { if (A == null || A.length == 0) return 0; int length = A.length; int[] dp = new int[length + 1]; for (int i = 1; i <= length; i++) { int max = 0; int leftBound = Math.max(i - K, 0); for (int j = i - 1; j >= leftBound; j--) { max = Math.max(max, A[j]); dp[i] = Math.max(dp[i], dp[j] + max * (i - j)); } } return dp[length]; } }
-
// OJ: https://leetcode.com/problems/partition-array-for-maximum-sum/ // Time: O(NK) // Space: O(N) class Solution { public: int maxSumAfterPartitioning(vector<int>& A, int K) { int dp[501] = {}, N = A.size(); for (int i = 0; i < N; ++i) { int mx = 0; for (int t = i, last = max(0, i + 1 - K); t >= last; --t) { mx = max(mx, A[t]); dp[i + 1] = max(dp[i + 1], dp[t] + mx * (i - t + 1)); } } return dp[N]; } };
-
# 1043. Partition Array for Maximum Sum # https://leetcode.com/problems/partition-array-for-maximum-sum/ class Solution: def maxSumAfterPartitioning(self, A: List[int], K: int) -> int: N = len(A) dp = [0] * (N + 1) for i in range(1, N + 1): mmax = 0 for k in range(1, min(i, K) + 1): mmax = max(mmax, A[i - k]) dp[i] = max(dp[i], dp[i - k] + mmax * k) return dp[N]