LeetCode-689 三个无重叠子数组的最大和
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays
题目描述
给你一个整数数组 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 * 104
1 <= nums[i] < 216
1 <= k <= floor(nums.length / 3)
解题思路
相信不少同学和我一样,看到题的第一反应就是这道题要用滑动窗口的方法来解。
最初的想法是使用贪心算法的思路,循环三次,每次找到没有被提取出来的子串中最大的那一个,但是做的过程中发现这样会破坏数组的顺序规律。比如nums = 1 6 8 7 7 1 8 1 k = 2的输入下,根据题意最终找出来的子串应该是,68 77 18,但是在贪心算法的思路下,就变成了87 18 16,出现这种情况的原因是用这种思路来找子串,仅仅考虑到了值最大这一条件,忽略了数字间的顺序关系。
于是产生了想法2.0,三个滑动窗口,同时进行滑动,分别记录每个窗口的和,如果三个窗口的和都是最大,那么总和一定是最大的,而由于三个窗口依次排列,所以理论上找出的子串应该都是可以保持顺序关系的,但是这种想法和第一种方法一样,找到最大值后会导致窗口停下,还是只考虑到局部最大,并没有考虑整体最大,并且,还可能三个窗口产生重叠。在更新一个窗口的时候,必须维护其他窗口,必须保证前窗口的尾部在后窗口的头部之前。
想法3.0就产生了,放弃局部的思想,将三个窗口间的关系利用总和来表示出了。首先将三个窗口分别设置为[0, k-1], [k, 2k-1], [2k, 3k-1],计算三个窗口分别的和,然后移动第一个窗口,如果移动后窗口的和大于原来的和,那么移动第一个窗口并且更新最大值。在假设第一个窗口基础上求第一个窗口和第二个窗口总和的最大值,这是非常关键的一步,如果仅仅求各自的最大值,就相当于人为割断了窗口间的联系,从而无法达到整体最大。如果第一和第二的总和大于之前的最大值,那么更新最大值,并且记录下这个时候窗口的位置。第三步同样也是在第一第二个窗口移动完的基础之上进行计算的,并且比较三个窗口的最大值与移动前最大值。如果大于移动前的最大值,那么记录移动后的窗口信息。
并且由于滑动窗口是三个窗口同步向前的,并没有停止的操作,所以保证了三个窗口不会发生重叠。
源码展示
class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
vector<int> iRet;
int iSum[3] = { 0 }, iMax[3] = { 0 }, iIndex = 0, iIndex1 = 0, iIndex2 = k;
iRet.resize(3);
for(int i = 2 * k; i < nums.size(); i++)
{
iSum[0] += nums[i - 2 * k];
iSum[1] += nums[i - k];
iSum[2] += nums[i];
if(i >= 3 * k - 1)
{
if(iSum[0] > iMax[0])
{
iMax[0] = iSum[0];
iIndex = i - 3 * k + 1;
}
if(iSum[1] + iMax[0] > iMax[1])
{
iMax[1] = iSum[1] + iMax[0];
iIndex1 = iIndex;
iIndex2 = i - 2 * k + 1;
}
if(iSum[2] + iMax[1] > iMax[2])
{
iMax[2] = iMax[1] + iSum[2];
iRet = {iIndex1, iIndex2, i - k + 1};
}
iSum[0] -= nums[i - 3 * k + 1];
iSum[1] -= nums[i - 2 * k + 1];
iSum[2] -= nums[i - k + 1];
} }
return iRet;
}
};
运行结果
最新文章
- css实现容器垂直水平居中的七中方法
- 【Java EE 学习 72 上】【数据采集系统第四天】【增加调查logo】【文件上传】【动态错误页指定】【上传限制】【国际化】
- Linux deepin 下sublimes配置g++ openGL
- 在Asp.Net MVC 中如何用JS访问Web.Config中appSettings的值
- 在HTML标签<;a/>;中调用javascript代码
- java中queue的使用
- android.mk文件里的通配符
- 顺序表(C++)
- vs2010安装路径解决不能修改的方法
- css实现选项卡
- Micropython TurnipBit 电子时钟 青少年编程入门
- Mac下更改JDK环境变量配置
- html input 文本框 只能输入数字,包含输小数点.
- PHP注释
- Linux - DDOS检测
- Compoxure 微服务组合proxy 中间件
- 使用pandas导入csv文件到MySQL
- Shark简介、部署及编译小结
- DOM EVENT
- PHP安全之register_globals (转)