LeetCode讲解篇之1043. 分隔数组以得到最大和
题目描述
题解思路
对于这题我们这么考虑，我们选择以数字的第i个元素做为分隔子数组的右边界，我们需要计算当前分隔子数组的长度为多少时能让数组[0, i]进行分隔数组的和最大
我们用数组f表示[0, i)区间内的分隔数组的最大和
那么数组[0, i]进行分隔数组的最大和 = 最后一个子数组区间分别为[i - 1, i]、 [i - 2, i]、 … 、[i - k + 1, i]时能得到[0, i]范围内分隔数组的最大值的最大值
即f[i] = f[j] + (i - j) * maxVal，其中j为最后一个子数组区间的左边界，maxVal为[j, i]范围内arr数组的最大值
题解代码
func maxSumAfterPartitioning(arr []int, k int) int {
n := len(arr)
// [0, i)区间内的分隔数组的最大和
f := make([]int, n + 1)
for i := 1; i <= n; i++ {
maxVal := arr[i - 1]
for j := i - 1; j >= 0 && j >= i - k; j-- {
f[i] = max(f[i], f[j] + (i - j) * maxVal)
if j > 0 && arr[j - 1] > maxVal {
maxVal = arr[j - 1]
}
}
}
return f[n]
}
题目链接
https://leetcode.cn/problems/partition-array-for-maximum-sum/
原文地址：https://blog.csdn.net/qq_67733273/article/details/142736432
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！