建设工程网站单位名单,小程序制作后维护成本,搜索引擎优化分析报告,wordpress事件提醒目录
689. 三个无重叠子数组的最大和
题目描述#xff1a;
实现代码与解析#xff1a;
dp
原理思路#xff1a;
滑动窗口#xff1a;
原理思路#xff1a; 689. 三个无重叠子数组的最大和
题目描述#xff1a; 给你一个整数数组 nums 和一个整数 k #xff0c;找…目录
689. 三个无重叠子数组的最大和
题目描述
实现代码与解析
dp
原理思路
滑动窗口
原理思路 689. 三个无重叠子数组的最大和
题目描述 给你一个整数数组 nums 和一个整数 k 找出三个长度为 k 、互不重叠、且全部数字和3 * k 项最大的子数组并返回这三个子数组。
以下标的数组形式返回结果数组中的每一项分别指示每个子数组的起始位置下标从 0 开始。如果有多个结果返回字典序最小的一个。
示例 1
输入nums [1,2,1,2,6,7,5,1], k 2
输出[0,3,5]
解释子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。示例 2
输入nums [1,2,1,2,1,2,1,2,1], k 2
输出[0,2,4]提示
1 nums.length 2 * 1041 nums[i] 2161 k floor(nums.length / 3)
实现代码与解析
dp
class Solution {
public:vectorint maxSumOfThreeSubarrays(vectorint nums, int k) {reverse(nums.begin(), nums.end());int n nums.size();vectorvectorint f(n 1, vectorint(4));// 计算前缀和vectorint s(n 1, 0); // 一般0位置空出来方便处理边界for (int i 1; i n; i) { // s[1] nums[0];s[i] s[i - 1] nums[i - 1]; }// dpfor (int i k; i n; i) {for (int j 1; j 4; j) {f[i][j] max(f[i - k][j - 1] s[i] - s[i - k], f[i - 1][j]);}}vectorint res;int j 3, i n;while (j 0) {if (f[i - 1][j] f[i - k][j - 1] s[i] - s[i - k]) i--;else {res.push_back(n - i);i - k; // 跳到前一个位置j--; }}return res;}
};
原理思路 众所周知dp一般是用来求结果的而不容易输出寻找的过程。
首先求一下前缀和 s。
dp数组含义 与01背包类似遍历到第 i 个数在第 j 次选取 或 不选取 的最大值。一共选3次。
用 i 来代表单个数组最后一个数的下标。
递推公式 f[i][j] max(f[i - k][j - 1] s[i] - s[i - k], f[i - 1][j]);
两种情况i 选取下标 i - k 的数 第 j 次不选取的最大值 此段数组的和。 i 不选取下标 i - 1第 j 次 选取后的最大值继承过来。 两者取一个max。
回溯寻找路径 利用递推公式我们判断每个数是通过max取的哪个值来求出路径。加入到res中。
注意 此题说明如果有多个结果返回字典序最小的一个。
所以我们反转数组或者倒着遍历数组不然会取到字典序大的。
滑动窗口
class Solution {
public:vectorint maxSumOfThreeSubarrays(vectorint nums, int k) {vectorint res(3);int sum1 0, maxSum1 0, idx1 0;int sum2 0, maxSum12 0, idx2 0, idx12_1 0, idx12_2 0;int sum3 0, maxSum123 0;for (int i k * 2; i nums.size(); i) {sum1 nums[i - k * 2];sum2 nums[i - k];sum3 nums[i];if (i k * 3 - 1) {if (sum1 maxSum1) {maxSum1 sum1;idx1 i - k * 3 1;}if (maxSum1 sum2 maxSum12) {maxSum12 maxSum1 sum2;idx12_1 idx1;idx12_2 i - k * 2 1;}if (maxSum12 sum3 maxSum123) {maxSum123 maxSum12 sum3;res {idx12_1, idx12_2, i - k 1};}sum1 - nums[i - k * 3 1];sum2 - nums[i - k * 2 1];sum3 - nums[i - k 1];}}return res;}
};
原理思路 这里记录一下我自己的问题。
为什么数组1和数组2为什么有一个idx1idx12_1 因为当数组1的sum为最大时idx1是一个值但是此时数组2与数组1的sum和并不一定是最大的毕竟要考虑数组之间的不重叠影响idx12_1用来记录最大的情况时的idx1而idx12_1要用idx1来赋值所以这就是两个idx的含义不同以及作用的不同。至于为什么数组3没有因为res就是变相的来记录了所以不需要单独再次记录当前想单独写也没问题。
