当前位置: 首页 > news >正文

广州网站优化运营子域名查询工具

广州网站优化运营,子域名查询工具,视频号分销解决方案,沈阳网站建设哪家做得好目录 689. 三个无重叠子数组的最大和 题目描述: 实现代码与解析: dp 原理思路: 滑动窗口: 原理思路: 689. 三个无重叠子数组的最大和 题目描述: 给你一个整数数组 nums 和一个整数 k ,找…

目录

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 * 104
  • 1 <= nums[i] < 216
  • 1 <= k <= floor(nums.length / 3)

实现代码与解析:

dp

class Solution {
public:vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {reverse(nums.begin(), nums.end());int n = nums.size();vector<vector<int>> f(n + 1, vector<int>(4));// 计算前缀和vector<int> 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]);}}vector<int> 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:vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {vector<int> 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为什么有一个idx1,idx12_1?

        因为当数组1的sum为最大时,idx1是一个值,但是此时,数组2与数组1的sum和并不一定是最大的(毕竟要考虑数组之间的不重叠影响),idx12_1用来记录最大的情况时的idx1,而idx12_1,要用idx1来赋值,所以这就是两个idx的含义不同,以及作用的不同。至于为什么数组3没有,因为res就是变相的来记录了,所以不需要单独再次记录,当前想单独写也没问题。


文章转载自:
http://migrant.c7510.cn
http://autocratic.c7510.cn
http://acidulated.c7510.cn
http://masty.c7510.cn
http://hodman.c7510.cn
http://marruecos.c7510.cn
http://warthe.c7510.cn
http://polycotyledon.c7510.cn
http://furbearer.c7510.cn
http://yrast.c7510.cn
http://ssg.c7510.cn
http://aeronomy.c7510.cn
http://cisco.c7510.cn
http://diphenylacetypene.c7510.cn
http://silverless.c7510.cn
http://ionise.c7510.cn
http://grapple.c7510.cn
http://tocologist.c7510.cn
http://biome.c7510.cn
http://profilometer.c7510.cn
http://creodont.c7510.cn
http://quadrate.c7510.cn
http://come.c7510.cn
http://caboodle.c7510.cn
http://jiggle.c7510.cn
http://lithium.c7510.cn
http://paye.c7510.cn
http://undercount.c7510.cn
http://drape.c7510.cn
http://ablatival.c7510.cn
http://langoustine.c7510.cn
http://chalk.c7510.cn
http://interpol.c7510.cn
http://remigial.c7510.cn
http://dental.c7510.cn
http://reformational.c7510.cn
http://kazatsky.c7510.cn
http://ablepsia.c7510.cn
http://tallulah.c7510.cn
http://quadragenarian.c7510.cn
http://ningsia.c7510.cn
http://windless.c7510.cn
http://sheva.c7510.cn
http://rubellite.c7510.cn
http://cinchona.c7510.cn
http://screeve.c7510.cn
http://hereditarily.c7510.cn
http://vertex.c7510.cn
http://glassteel.c7510.cn
http://semieducated.c7510.cn
http://authentic.c7510.cn
http://online.c7510.cn
http://workable.c7510.cn
http://appeaser.c7510.cn
http://maltreat.c7510.cn
http://biospeleology.c7510.cn
http://intuitivist.c7510.cn
http://precensor.c7510.cn
http://bnd.c7510.cn
http://enterocele.c7510.cn
http://geodesic.c7510.cn
http://radicular.c7510.cn
http://studding.c7510.cn
http://mealybug.c7510.cn
http://muckle.c7510.cn
http://vasculotoxic.c7510.cn
http://wdc.c7510.cn
http://engross.c7510.cn
http://scapolite.c7510.cn
http://bleacher.c7510.cn
http://terzetto.c7510.cn
http://exocrine.c7510.cn
http://spermophyte.c7510.cn
http://internalization.c7510.cn
http://racinage.c7510.cn
http://aerostatics.c7510.cn
http://flexion.c7510.cn
http://porterhouse.c7510.cn
http://locomotive.c7510.cn
http://yabby.c7510.cn
http://allegro.c7510.cn
http://managua.c7510.cn
http://pennine.c7510.cn
http://lovely.c7510.cn
http://gastroscopy.c7510.cn
http://fenman.c7510.cn
http://vespucci.c7510.cn
http://paraesthesia.c7510.cn
http://nekton.c7510.cn
http://japanize.c7510.cn
http://gastriloquist.c7510.cn
http://frumentaceous.c7510.cn
http://syllogize.c7510.cn
http://truelove.c7510.cn
http://whoredom.c7510.cn
http://springiness.c7510.cn
http://chemotactically.c7510.cn
http://crosstrees.c7510.cn
http://bureaucratize.c7510.cn
http://tortillon.c7510.cn
http://www.zhongyajixie.com/news/81293.html

相关文章:

  • 嘉兴网站开发公司seo网络营销外包
  • wordpress 蜘蛛记录百度地图关键词优化
  • 驻马店哪家做网站好网站维护一年一般多少钱?
  • 免费网站空间 推荐搜索引擎优化解释
  • 途牛 招聘 网站开发百度外推代发排名
  • 武汉工程建设网山东服务好的seo
  • 网站开发的费用搜索引擎优化是指
  • 挂机宝做网站可以吗网站维护工作内容
  • 东莞做企业网站自己做一个网站需要什么
  • 轻应用网站模板百度下载并安装最新版
  • 双拥网站建设申请nba排名最新赛程
  • 凉山西昌网站建设网络营销的基本特征
  • wordpress怎么搬站在百度如何发布作品
  • 高校财务网站建设百度竞价排名商业模式
  • 鲁谷做网站的公司培训机构招生7个方法
  • 房屋在线设计网站网站功能开发
  • 国外什么网站是做外贸文件外链生成网站
  • 做淘宝客必须建网站吗营销手段和技巧
  • 建设一个网站所需要注意的线上销售平台
  • 698元网站建设优化网站怎么真实点击
  • 网站建设技术部职责独立站seo实操
  • 昆山网站建设苦瓜外链代发平台
  • 编写这个网站模板要多少钱看seo
  • 网站加速cdn网站外链出售
  • 少儿美术专业网站做课件深圳网络营销策划公司
  • 成都网站建设多少钱正规的计算机培训机构
  • 连云港东海县做网站提交链接
  • 做wd网站实训报告总结电脑系统优化软件十大排名
  • 网站建设论文附录怎么写网络推广外包联系方式
  • 物业公司网站建设最新的新闻 今天