_1043.java

packagecom.fishercoder.solutions.secondthousand;

publicclass_1043 {
publicstaticclassSolution1 {
/*
 * credit: https://leetcode.com/problems/partition-array-for-maximum-sum/discuss/290863/JavaC%2B%2BPython-DP
 */
publicintmaxSumAfterPartitioning(int[] A, intK) {
intN = A.length;
int[] dp = newint[N];
for (inti = 0; i < N; i++) {
intcurMax = 0;
for (intk = 1; k <= K && i - k + 1 >= 0; k++) {
curMax = Math.max(curMax, A[i - k + 1]);
dp[i] = Math.max(dp[i], (i >= k ? dp[i - k] : 0) + curMax * k);
 }
 }
returndp[N - 1];
 }
 }
}