leetcode刷题详解—— 环形子数组的最大和

1. 题目链接:918. 环形子数组的最大和

2. 题目描述:

给定一个长度为 n环形整数数组 nums ,返回 nums 的非空 子数组 的最大可能和

环形数组 意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i + 1) % n]nums[i] 的前一个元素是 nums[(i - 1 + n) % n]

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上,对于子数组 nums[i], nums[i + 1], ..., nums[j] ,不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n

示例 1:

输入:nums = [1,-2,3,-2]
输出:3
解释:从子数组 [3] 得到最大和 3

示例 2:

输入:nums = [5,-3,5]
输出:10
解释:从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3:

输入:nums = [3,-2,2,-3]
输出:3
解释:从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

提示:

  • n == nums.length
  • 1 <= n <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104

3. 解法(动态规划)

3.1 算法思路:

请添加图片描述

1. 状态表示:

f[i]表示:以i为结尾的所有子数组中的最大和

g[i]表示:以i做结尾的所有子数组中和的最和

请添加图片描述

2. 状态转移方程:

请添加图片描述

3. 初始化:

可以在最前面加上一个辅助结点,帮助我们完成初始化。使用这种技巧要注意两点:

  1. 辅助结点里面的值要保证后续填表是正确的
  2. 下标的映射关系

请添加图片描述

4. 填表顺序:

根据状态转移方程,填表顺序为从左往右

5. 返回值

  1. 先找到f表里面的最大值->fmax
  2. 再找到g表里面的最小值->gmin
  3. 统计所有元素的和->sum
  4. 返回 sum==gmin?fmax:max(fmax,sum-gmin)

3.2 C++算法代码:

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        // 获取数组长度
        int n = nums.size();
        // 初始化两个辅助数组f和g,长度为n+1
        vector<int> f(n + 1), g(n + 1);
        // 初始化最大子数组和fmax、最小子数组和gmin、数组元素和sum
        int fmax = INT_MIN, gmin = INT_MAX, sum = 0;
        // 遍历数组
        for (int i = 1; i <= n; i++) {
            // 获取当前元素值
            int x = nums[i - 1];
            // 更新f数组:f[i]表示以nums[i-1]结尾的最大子数组和
            f[i] = max(x, x + f[i - 1]);
            // 更新fmax:记录所有位置上的最大子数组和
            fmax = max(fmax, f[i]);
            // 更新g数组:g[i]表示以nums[i-1]结尾的最小子数组和
            g[i] = min(x, x + g[i - 1]);
            // 更新gmin:记录所有位置上的最小子数组和
            gmin = min(gmin, g[i]);
            // 更新sum:记录数组元素之和
            sum += x;
        }
        // 如果sum等于gmin,说明整个数组都是负数,此时最大子数组和为fmax;否则,最大子数组和为fmax和sum-gmin中的较大值
        return sum == gmin ? fmax : max(fmax, sum - gmin);
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/209173.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SAP 如何检查已安装的SAP UI5 版本

第一个方法是直接从FLP中查看 但是部分高版本的FLP中没有这个about&#xff0c; 那么在当前界面可以使用&#xff1a;CTRL ALT SHIFT S 查看当前版本 根据此版本&#xff0c;去进行你的UI5的开发吧

NodeJS(二):npm包管理工具、yarn、npx、pnpm工具等

目录 (一)npm包管理工具 1.了解npm 2.npm的配置文件 常见的配置属性 scripts属性*** 依赖的版本管理 3.npm安装包的细节 4.package-lock文件 5.npm install原理** 6.npm的其他命令 (二) 其他包管理工具 1.yarn工具 基本指令 2.cnpm工具 3.npx工具 (1)执行本地…

C++可表示的数(数组前面2个数的和)

void 可表示的数&#xff08;数组前面2个数的和&#xff09;() {int aa[]{1,2,3,4,5,6,7,8,9}, j 0, z 1, jj z, n 9, ge 0;string a "";while (j < n)//缘由https://bbs.csdn.net/topics/396063706?page1#post-410898529{if (jj < n)if (aa[j] aa[z] …

Android--Jetpack--Lifecycle详解

富贵本无根&#xff0c;尽从勤里得 一&#xff0c;定义 Lifecycle 是一个具备宿主生命周期感知能力的组件。它持有组件&#xff08;Activity/Fragment&#xff09;生命周期状态信息&#xff0c;并且允许其观察者监听宿主生命周期状态变化。 顾名思义&#xff0c;Lifecycle的主…

数据治理的具体应用

数据治理架构 图 13 描述的是公安数据治理框架&#xff0c;平台架构主要包括数据存储、数据计算、数据管理、数据应用这 4 个部分。 (1) 数据存储&#xff1a; 基于分布式的大数据存储平台&#xff0c;具有很强的存储能力和扩张能力&#xff1b; (2) 数据计算&#xff1a; …

目标检测——Faster R-CNN算法解读

论文&#xff1a;Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks 作者&#xff1a;Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun 链接&#xff1a;https://arxiv.org/abs/1506.01497 代码&#xff1a;https://github.com/rbgirsh…

golang Pool实战与底层实现

使用的go版本为 go1.21.2 首先我们写一个简单的Pool的使用代码 package mainimport "sync"var bytePool sync.Pool{New: func() interface{} {b : make([]byte, 1024)return &b}, }func main() {for j : 0; j < 10; j {obj : bytePool.Get().(*[]byte) // …

Python 重要数据类型

目录 列表 序列操作 列表内置方法 列表推到式 字典 声明字典 字典基本操作 列表内置方法 字典进阶使用 字典生成式 附录 列表 在实际开发中&#xff0c;经常需要将一组&#xff08;不只一个&#xff09;数据存储起来&#xff0c;以便后边的代码使用。列表就是这样的…

JNPF低代码平台详解 -- 系统架构

目录 一、技术介绍 技术架构 二、设计原理 三、界面展示 1.代码生成器 2.工作流程 3.门户设计 4.大屏设计 5.报表设计 6.第三方登录 7.多租户实现 8.分布式调度 9.消息中心 四、功能框架 JNPF低代码是一款新奇、实用、高效的企业级软件开发工具&#xff0c;支持企…

柱状展示当中 ,如何给每个位置加多个项的办法

<!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title>双柱修改</title> <script src"https://cdn.staticfile.org/Chart.js/3.9.1/chart.js"></script> </head> <body><canvas i…

分治算法——912. 排序数组

文章目录 &#x1f348;1. 题目&#x1f34c;2. 算法原理&#x1f34f;3. 代码实现 &#x1f348;1. 题目 题目链接&#xff1a;912. 排序数组 - 力扣&#xff08;LeetCode&#xff09; 给你一个整数数组 nums&#xff0c;请你将该数组升序排列。 示例 1&#xff1a; 输入&am…

【Vulnhub 靶场】【Funbox: Lunchbreaker】【简单】【20210522】

1、环境介绍 靶场介绍&#xff1a;https://www.vulnhub.com/entry/funbox-lunchbreaker,700/ 靶场下载&#xff1a;https://download.vulnhub.com/funbox/FunboxLunchbreaker.ova 靶场难度&#xff1a;简单 发布日期&#xff1a;2021年05月22日 文件大小&#xff1a;1.6 GB 靶…

java: 警告: 源发行版 17 需要目标发行版 17

这是一个编译期的报错提示 源发行版 17 , 即说明你的maven项目当前指定的编译版本是jdk17&#xff0c;需要目标发行版 17则是说明你的idea中实际选择的jdk版本并非17 检查你项目中的pom文件中的配置 <properties><java.version>17</java.version><prop…

localStorage 和sessionStorage

localStorage 和 sessionStorage 是浏览器提供的两种客户端存储数据的方式&#xff1a; 生命周期&#xff1a; localStorage&#xff1a; 存储在 localStorage 中的数据在浏览器关闭后仍然保留&#xff0c;直到被显式删除或浏览器清除缓存。sessionStorage&#xff1a; 存储在 …

2023年12月2日历史上的今天大事件早读

823年12月2日 《门罗宣言》发表 1908年12月2日 末代皇帝溥仪登基 1919年12月2日 平江开展驱除湘督张敬尧运动 1929年12月2日 北平周口店发现中国猿人头盖骨 1941年12月2日 美裔华人物理学家朱经武出生 1949年12月2日 中央决定发行人民胜利公债 1952年12月2日 拿破仑三世成…

mac 系统 vmware 安装centos8

选择镜像 安装系统 依次设置有告警的项目 设置用户名密码 设置root密码 重启系统 重启成功进入下面界面 勾选&#xff0c;点击done 点击箭头所指按钮 输入密码登录 安装成功了 设置网络 打开终端 切换root用户 输入下面指令 su root 输入root的密码 安装git

Python爬虫-新能源汽车销量榜

前言 本文是该专栏的第11篇,后面会持续分享python爬虫案例干货,记得关注。 本文以懂车平台的新能源汽车销量榜单为例,获取各车型的销量排行榜单数据。具体实现思路和详细逻辑,笔者将在正文结合完整代码进行详细介绍。 废话不多说,跟着笔者直接往下看正文详细内容。(附带…

python的制图

测试数据示例&#xff1a; day report_user_cnt report_user_cnt_2 label 2023-10-01 3 3 欺诈 2023-10-02 2 4 欺诈 2023-10-03 6 5 欺诈 2023-10-04 2 1 正常 2023-10-05 4 3 正常 2023-10-06 4 4 正常 2023-10-07 2 6 正常 2023-10-08 3 7 正常 2023-10-09 3 12 正常 2023-…

jetpack compose——圆角、渐变

一、背景圆角、渐变 效果图&#xff1a; 代码为&#xff1a; Box(modifier Modifier.clip(RoundedCornerShape(14.dp)) // 设置圆角半径.background(brush Brush.horizontalGradient( // 设置渐变色listOf(Color(0xFFF5DEC9),Color(0xFFF7A74C),))).constrainAs(box_bottom…

杨志丰:OceanBase助力企业应对数据库转型深水区挑战

11 月 16 日&#xff0c;OceanBase 在北京顺利举办 2023 年度发布会&#xff0c;正式宣布&#xff1a;将持续践行“一体化”产品战略&#xff0c;为关键业务负载打造一体化数据库。OceanBase 产品总经理杨志丰发表了《助力企业应对数据库转型深水区挑战》主题演讲。 以下为演讲…