每日一题：分隔数组以得到最大和 - 刷题题解

给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

题目链接：https://leetcode.cn/problems/partition-array-for-maximum-sum/

动态规划：

dp[i] 表示以 arr 前 i+1 （i 从 0 开始）个元素分组之后所能得到的最大数组和。

当 i<k 时，很明显最大和就是 dp[i] = max(arr[0...i]) * (i+1)
当 i>=k 时， dp[i] = max(dp[j-1] + max(arr[i-j+1 ... i]) * (i-j+1) ，其中 i-k < j <= i

	class Solution {
	public int maxSumAfterPartitioning(int[] arr, int k) {
	int n = arr.length;
	//dp [i] 表示以 arr [i] 结尾分割的最大和
	int[] dp = new int[n];

	// 当 i < k 时，分成一组即可获得最大的和
	int maxVal = 0;
	for (int i = 0; i < k; ++i) {
	maxVal = Math.max(maxVal, arr[i]);
	dp[i] = maxVal * (i + 1);
	}

	for (int i = k; i < n; ++i) {
	maxVal = arr[i];
	// 枚举 k 个分割点的，获取最大和
	for (int j = i; j >= 0 && j > i - k; --j) {
	maxVal = Math.max(arr[j], maxVal);
	dp[i] = Math.max(dp[i], dp[j - 1] + (i - j + 1) * maxVal);
	}
	}

	return dp[n - 1];
	}
	}