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

2023-10-15 13:12

本文主要是介绍动态规划: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. 环形子数组的最大和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/217948

相关文章

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序