动态规划:918. 环形子数组的最大和

个人主页 : 个人主页
个人专栏 : 《数据结构》 《C语言》《C++》《算法》
文章目录
- 前言
- 一、题目解析
- 二、解题思路
- 解题思路
- 状态表示
- 状态转移方程
- 初始化
- 填表顺序
- 返回值
- 三、代码实现
- 总结
前言
本篇文章仅是作为小白的我的一些理解,,如果有错误的地方,希望大佬们指出。
918. 环形子数组的最大和
一、题目解析

求环型数组中连续子数组最大和。
二、解题思路
解题思路
关于子数组的最大和,其有两种情况。

对于情况1而言,我们只需要正常使用dp求最大子数组和即可。
对于情况2而言,如果我们使用前缀和 与 后缀和 求和来求最大子数组和就相对麻烦,但如果我们先求最小子数组和呢?

情况二:求最大子数组和,就可以转换为数组和(sum) - 最小子数组和。
状态表示
该题的状态表示:经验(以该位置为终点 / 以该位置为起点) + 题目要求

那么对于情况1记为 f() ,f [ i ]表示以 i 位置为终点的所以子数组的最大和。
那么对于情况2记为 g(),g [ i ]表示以 i 位置为终点的所以子数组的最小和。
状态转移方程
情况1
对于在数组 i 位置的元素,我们可以将其分成两个状态。

即 f [i]的长度等于1,和 f [i]的长度大于1。
当 f [i]的长度等于1时,此时子数组最大和不就是该元素的大小,即f [i] = nums[i]
当 f [i]的长度大于1时,此时子数组最大和不就是 之前子数组最大和(f[i-1]) + 该元素大小,即f[i] = f[i-1] + nums[i]
那么我们对这两种情况取最大值即可得 f [ i ] 的状态转移方程。

情况2
和情况1类似,对于情况2,我们同样可以以 i位置,分成两种状态。

即 g [i]的长度等于1,和 g [i]的长度大于1。
当 g [i]的长度等于1时,此时子数组最小和不就是该元素的大小,即g [i] = nums[i]
当 g [i]的长度大于1时,此时子数组最小和不就是 之前子数组最小和(g[i-1]) + 该元素大小,即g[i] = g[i-1] + nums[i]
那么我们对这两种状态取最小值,既可以得到 g [i]的状态转移方程

初始化
我们要求 f [i]就要先知道 f [i -1],但如果当 i = 0时,f [i-1]就会越界。那么我们虚拟一块空间,将整个 f[i] 后移一个位置。如下所示:

如果我们进行这样的操作,有两点需要注意。
- 如何填写 f[0]保证后续填表结果正确?
只要f[0] = 0即可,毕竟f[1] = max(f[0], f[0]+nums[0])此时f[0] == f[0] + nums[0] - 映射关系
因为整个f[i]后移了一个,所以f[i] 所对应的元素 nums[i]相对前移了,即f[i] 与 nums[i-1]的元素相对应。
填表顺序
要求f[i],就要先知道f[i-1],那么我们就要从前向后遍历数组nums,来填表。
返回值
我们只需要 返回情况1 与 情况2 的最大值即可。
但对于{-1, -2, -3, -4}而言,情况2 的值是:sum(-10) - gmin(-10)等于0,情况1 的值是:fmax(-1)。那么返回值就是0,结果错误。所以要先判断gmin == sum,如果相等,表示此时数组全是负数,返回fmax即可。如果不相等,返回情况1 与 情况2 的最大值即可。
三、代码实现
class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();vector<int> f(n+1), g(n+1);int fmax = INT_MIN, gmin = INT_MAX, sum = 0;for(int i = 1; i <= n; i++){f[i] = max(f[i-1] + nums[i-1], nums[i-1]);fmax = max(f[i], fmax);g[i] = min(g[i-1] + nums[i-1], nums[i-1]);gmin = min(g[i], gmin);sum += nums[i-1];}return sum == gmin? fmax: max(fmax, sum - gmin);}
};
总结
以上就是我对于环形子数组的最大和的理解。感谢支持!!!

相关文章:
动态规划:918. 环形子数组的最大和
个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》《C》《算法》 文章目录 前言一、题目解析二、解题思路解题思路状态表示状态转移方程初始化填表顺序返回值 三、代码实现总结 前言 本篇文章仅是作为小白的我的一些理解,,…...
毅速丨模具3D打印材料有哪些选择
当前1.2709和CX是市面上最常用的3D打印模具钢材料,模具3D打印有没有更多的材料选择呢? 据了解,上海毅速推出的几款3D打印新材料正在被越来越多的行业所采用。如毅速的EM191S高性能高抛光不锈钢粉末,这款材料的抗开裂和耐腐蚀性能是…...
Springcloud笔记(1)-微服务和springcloud介绍
微服务简介 就是将一个大的应用,拆分成多个小的模块,每个模块都有自己的功能和职责,每个模块可以 进行交互,这就是微服务对于微服务,业界没有严格统一的定义,但是作为“微服务”这名词的发明人,…...
十六、代码校验(4)
本章概要 调试 使用 JDB 调试图形化调试器 调试 尽管聪明地使用 System.out 或日志信息能给我们带来对程序行为的有效见解,但对于困难问题来说,这种方式就显得笨拙且耗时了。 你也可能需要更加深入地理解程序,仅依靠打印日志做不到。此时…...
【已解决】No Python at ‘D:\Python\python.exe‘
起因,我把我的python解释器,重新移了个位置,导致我在Pycharm中的爬虫项目启动,结果出现这个问题。 然后,从网上查到了这篇博客: 【已解决】No Python at ‘D:\Python\python.exe‘-CSDN博客 但是,按照上述…...
蓝桥杯双周赛算法心得——数树数(dfs)
大家好,我是晴天学长,一个简单的dfs思想,需要的小伙伴可以关注支持一下哦!后续会继续更新的。 1) .数树数 2) .算法思路 代码的主要逻辑是: 1.使用Scanner读取输入的整数n和q,其中n表示测试用例的数量&am…...
综述:大规模小目标检测
论文地址: Towards Large-Scale Small Object Detection: Survey and Benchmarksarxiv.org/abs/2207.14096 目录 摘要 1.Introduction 1.1 与之前综述的比较 1.2 总结 2.小目标检测回顾 2.1 问题定义 2.2 主要挑战 2.3 小目标检测算法回顾 3.小目标检测的数据集 …...
ORACLE XXX序列 goes below MINVALUE 无法实例化的处理办法
--序列增加区分 --删除未使用序列表 DECLARE V_CNT INT; BEGINSELECT COUNT(*) INTO V_CNT FROM USER_SEQUENCES WHERE SEQUENCE_NAME SEQ_INTELLECT_BIZ_DETAIL_ID;IF V_CNT1 THEN BEGINEXECUTE IMMEDIATE DROP SEQUENCE SEQ_INTELLECT_BIZ_DETAIL_ID;END;END IF; END; / ---…...
6款流程图制作软件:一站式指南
流程图是一种常用的图示工具,可以帮助我们更清晰地表达和展示流程、流程图等内容。在今天已经变得非常普及和便捷,接下来本文将于大家分享6款好用的流程图软件,一起来看看吧! 博思白板boardmix 博思白板boardmix是一款基于浏览器…...
第三章:Python中的序列(上)
Python中的序列 是一种有序的数据结构,通常用于存储一组相关的元素。Python中的序列包括列表(list)、元组(tuple)和字符串(string)。 1. 列表 是最常用的序列类型,它是可变的(即可以添加、删除和修改元素)。列表中的元素可以是任何类型,包括其他列表或元组。列表…...
使用.NET实现WOL唤醒远程开机
文章目录 1. 背景2. 关于 WOL2.1 WOL 工作原理2.2 开启网卡唤醒功能 3. 快速验证3.1 局域网 Wake on Lan 应用3.2 Ubuntu 的 etherwake 命令4. 代码实现4.1 创建.NET控制台应用程序4.2 编写代码4.3 运行应用程序 5. 最后 1. 背景 家居自动化是现代智能家居的重要组成部分&…...
适用于 Golang 的任务调度程序 AGScheduler
以前一直使用 Python 的任务调度库 APScheduler(支持任务持久化,支持多种存储方式),但由于没有找到和它功能和使用方式类似的 Golang 库,所以模仿 APScheduler 3.x 写了个简易版本的 AGScheduler。 AGScheduler Advan…...
【HCIP】HCIA复习
目录 大纲 情景代入 访问百度/谷歌服务器的准备工作 1、计算机网络发展第一阶段人机交互的加工过程 2、OSI参考模型 3、TCP/IP参考模型 访问谷歌(百度)服务器的流程 1、主机需要一个IP地址才能上网(本场景中通过DHCP服务获取IP地址&a…...
【Python小项目之Tkinter应用】【实用工具】实现手写签名器,可选线条粗细,支持清空、撤销、恢复功能,可将写好的签名保存成图片
文章目录 前言一、实现思路二、关键代码三、完整代码总结同系列项目文章:前言 老规矩,先看效果: 在手写签名窗口中,用户可以选择线条粗细来签名,点击清空按钮可以清空画布,点击撤销按钮可以撤销一笔,点击恢复按钮可以撤销上一步进行的清空或撤销操作,点击保存按钮可以…...
Jenkins集成newman
一、Docker环境准备 二、Jenkins环境准备 三、登录Jenkins 安装NodeJs插件 四、Jenkins全局工具配置Nodejs 五、创建Jenkins自由风格项目 构建步骤1:选择Execute NodeJS script构建步骤2:选择执行shell脚本 六、将postman相关的脚本、环境变量数据、全局…...
Excel——对其他工作表和工作簿的引用
一、引用其他sheet页表区域 若希望在公式中引用其他工作表的单元格区域,可以在公式编辑状态下,通过鼠标单击相应的工作表标签,然后选择相应的单元格区域。 例1 跨sheet页引用其他工作表区域 如图1所示的工作表Sheet2为工资表。 在Sheet1表…...
如何正确的防止服务器被攻击?103.216.153.x
网站服务器被攻击是新建网站常常发生的事情,对于新手来说这也是非常棘手的问题。那么一旦遇到这样的情况,我们需要如何解决呢?怎么才能防止服务器被攻击,怎么保障自己网站信息的安全,如果发现被攻击又该怎么做呢&#…...
本地生活将成快手新的营收增长点
监制 | 何玺 排版 | 叶媛 快手本地生活开始强化B端市场。 据了解,快手 “本地商家”APP已经正式上线。这是快手为本地生活商家推出的独立工作平台,有助于商家提升经营效率。 新APP的上线,标志着快手本地生活业务布局,正从过去侧…...
信息化工程测试验收管理制度
1、总则 1.1、目的 为规范XXXXX单位的信息系统建设和工程项目测试验收准则,特制订本管理制度。 1.2、范围 本制度适用于XXXXX单位工程测试验收管理。 1.3、职责 信息系统建设和其他信息系统工程类项目的测试和验收主要由项目负责人负责,必要的时候…...
解决vue2设置cross-env设置环境变量不起作用问题
1. 配置package.json package.json的scripts里增加打包脚本 "build-app": "cross-env VUE_APP_LOGIN_VALUEapp NODE_OPTIONS--max_old_space_size4096 node build/build.js",2.配置webpack.prod.conf.js webpack.prod.conf.js的plugins里增加脚本 new …...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
