[LeetCode] 1043. Partition Array for Maximum Sum 分隔数组以得到最大和
Given an integer array arr
, you should 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: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]
Example 2:
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
Example 3:
Input: arr = [1], k = 1
Output: 1
Constraints:
1 <= arr.length <= 500
0 <= arr[i] <= 109
1 <= k <= arr.length
这道题给了一个数组 arr,和一个正整数k,说是将数组分成若干个长度不超过k的子数组,分割后的子数组所有的数字都变成该子数组中的最大值,让求分割后的所有子数组数字之和。由于分割的子数组长度不固定,用暴力搜索的话将会有很多很多种情况,不出意外的话会超时。对于这种玩子数组,又是求极值的题,刷题老司机们应该立马就能想到用动态规划 Dynamic Programming 来做。先来定义 dp 数组,先从最简单的考虑,使用一个一维的 dp 数组,其中 dp[i] 就表示分割数组中的前i个数字组成的数组可以得到的最大的数字之和。下面来考虑状态转移方程怎么求,对于 dp[i] 来说,若把最后k个数字分割出来,那么前i个数字就被分成了两个部分,前 i-k 个数字,其数字之和可以直接由 dp[i-k] 来取得,后面的k个数字,则需要求出其中最大的数字,然后乘以k,用这两部分之和来更新 dp[i] 即可。由于题目中说了分割的长度不超过k,那么就是说小于k的也是可以的,则需要遍历 [1, k] 区间所有的长度,均进行分割。接下来看代码,建立一个大小为 n+1 的 dp 数组,然后i从1遍历到n,此时新建一个变量 curMax 记录当前的最大值,然后用j从1遍历到k,同时要保证 i-j 是大于等于0的,因为需要前半部分存在,实际上这是从第i个数字开始往前找j个数字,然后记录其中最大的数字 curMax,并且不断用 dp[i-j] + curMax * j
来更新 dp[i] 即可,参见代码如下:
class Solution {
public:
int maxSumAfterPartitioning(vector<int>& arr, int k) {
int n = arr.size();
vector<int> dp(n + 1);
for (int i = 1; i <= n; ++i) {
int curMax = 0;
for (int j = 1; j <= k && i - j >= 0; ++j) {
curMax = max(curMax, arr[i - j]);
dp[i] = max(dp[i], dp[i - j] + curMax * j);
}
}
return dp[n];
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1043
参考资料:
https://leetcode.com/problems/partition-array-for-maximum-sum/
相关文章
- Leetcode: Unique Substrings in Wraparound String
- 【LeetCode-面试算法经典-Java实现】【033-Search in Rotated Sorted Array(在旋转数组中搜索)】
- LeetCode高频题:客栈选择问题,总共有多少种选择住宿的方案,保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚
- LeetCode高频题53. 最大子数组和,具有最大和的连续子数组,返回其最大和
- [LeetCode]1437. 是否所有 1 都至少相隔 k 个元素
- [LeetCode]167. 两数之和 II - 输入有序数组
- [LeetCode]剑指 Offer 03. 数组中重复的数字
- LeetCode 167. 两数之和 II - 输入有序数组
- LeetCode数据结构_C语言题解系列-数组
- 201、【数组】leetcode ——面试题 17.05. 字母与数字(C++版本)
- 178、【数组/动态规划】leetcode ——392. 判断子序列:双指针+动态规划(C++版本)
- 159、【动态规划】leetcode ——322. 零钱兑换:二维数组+一维滚动数组(C++版本)
- 141、【贪心算法】leetcode ——56. 合并区间(区间重叠解法+双指针解法)(C++版本)
- 133、【贪心算法】leetcode ——1005. K 次取反后最大化的数组和(模拟变化+贪心策略)(C++版本)
- 【leetcode】61: 旋转链表
- [LeetCode] 829. Consecutive Numbers Sum 连续数字之和
- [LeetCode] 912. Sort an Array 数组排序
- [LeetCode] 905. Sort Array By Parity 按奇偶排序数组
- [LeetCode] 878. Nth Magical Number 第N个神奇数字
- [LeetCode] 763. Partition Labels 分割标签
- [LeetCode] 560. Subarray Sum Equals K 子数组和为K
- [LeetCode] 525. Contiguous Array 相连的数组
- [LeetCode] 496. Next Greater Element I 下一个较大的元素之一
- [LeetCode] Sort Characters By Frequency 根据字符出现频率排序
- [LeetCode] Serialize and Deserialize BST 二叉搜索树的序列化和去序列化
- [LeetCode] Find All Duplicates in an Array 找出数组中所有重复项
- [LeetCode] Patching Array 补丁数组
- [LeetCode] 289. Game of Life 生命游戏
- [LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二
- leetcode 167. Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组