LeetCode-day21-1186. 删除一次得到子数组最大和

LeetCode-day21-1186. 删除一次得到子数组最大和

  • 题目描述
  • 示例
    • 示例1:
    • 示例2:
    • 示例3:
  • 思路
  • 代码

题目描述

给你一个整数数组,返回它的某个 非空 子数组(连续元素)在执行一次可选的删除操作后,所能得到的最大元素总和。换句话说,你可以从原数组中选出一个子数组,并可以决定要不要从中删除一个元素(只能删一次哦),(删除后)子数组中至少应当有一个元素,然后该子数组(剩下)的元素总和是所有子数组之中最大的。

注意,删除一个元素后,子数组 不能为空

示例

示例1:

输入:arr = [1,-2,0,3]
输出:4
解释:我们可以选出 [1, -2, 0, 3],然后删掉 -2,这样得到 [1, 0, 3],和最大。

示例2:

输入:arr = [1,-2,-2,3]
输出:3
解释:我们直接选出 [3],这就是最大和。

示例3:

输入:arr = [-1,-1,-1,-1]
输出:-1
解释:最后得到的子数组不能为空,所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
我们应该直接选择 [-1],或者选择 [-1, -1] 再从中删去一个 -1。

思路

采用动态规划的记忆化搜索+递推,优化后使用空间优化
状态转移方程为:
在这里插入图片描述

代码

class Solution:def maximumSum(self, arr: List[int]) -> int:ans = f0 = f1 = -inffor x in arr:f1 = max(f1+x,f0)f0 = max(f0,0)+xans = max(ans,f0,f1)return ans

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Springcloud之gateway的使用详解

官网地址&#xff1a;https://docs.spring.io/spring-cloud-gateway/docs/4.0.4/reference/html/ 1.网关入门 helloword 网关不依赖start-web 导入的pom&#xff1a; <!--gateway--> <dependency><groupIdorg.springframework.cloud</groupId><arti…

JAVA零基础学习2(算术逻辑三元运算符、原码反码补码、标准的类如何描写)

JAVA零基础学习2&#xff08;算术逻辑三元运算符、原码反码补码、标准的类如何描写&#xff09; 算术运算符算术运算符自增和自减运算符算术运算符的优先级示例代码 逻辑运算符三元运算符示例代码示例1&#xff1a;简单的条件判断示例2&#xff1a;嵌套的三元运算符 原码反码补…

贪吃蛇超精讲(C语言)

前言 如果你还是个萌新小白&#xff0c;那么该项目的攻克过程一定会十分艰难。虽然作者已经将文章尽可能写的逻辑清晰&#xff0c;内容详细。但所谓“纸上得来终觉浅”&#xff0c;在讲到陌生结构和函数时&#xff0c;大家请一定自己动手去敲一遍代码&#xff0c;这很重要&…

一次Golang单体架构中的复杂长函数的重构实践和思考

在现代应用程序开发中&#xff0c;信息流&#xff08;Feed&#xff09;是许多平台核心功能的一部分。信息流往往会聚合大量的数据&#xff0c;构建这样一个信息流列表是一个复杂的任务。需要从多个微服务和数据库中获取大量数据&#xff0c;包括用户、频道、标签、等级、用户状…

【Langchain大语言模型开发教程】基于文档问答

&#x1f517; LangChain for LLM Application Development - DeepLearning.AI Embedding&#xff1a; https://huggingface.co/BAAI/bge-large-en-v1.5/tree/main 学习目标 1、Embedding and Vector Store 2、RetrievalQA 引包、加载环境变量 import osfrom dotenv import…

react开发-配置开发时候@指向SRC目录

这里写目录标题 配置开发时候指向SRC目录VScode编辑器给出提示总体1.配置react的 2.配置Vscode的1.配置react的2,配置VSCode的提示支持 配置开发时候指向SRC目录VScode编辑器给出提示 总体1.配置react的 2.配置Vscode的 1.配置react的 1. 我么需要下载一个webpack的插件 这样…

Java案例斗地主游戏

目录 一案例要求&#xff1a; 二具体代码&#xff1a; 一案例要求&#xff1a; &#xff08;由于暂时没有学到通信知识&#xff0c;所以只会发牌&#xff0c;不会设计打牌游戏&#xff09; 二具体代码&#xff1a; Ⅰ&#xff1a;主函数 package three;public class test {…

filebeat,kafka,clickhouse,ClickVisual搭建轻量级日志平台

springboot集成链路追踪 springboot版本 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.6.3</version><relativePath/> <!-- lookup parent from…

CentOS 7报错:yum命令报错 “ Cannot find a valid baseurl for repo: base/7/x86_6 ”

参考连接&#xff1a; 【linux】CentOS 7报错&#xff1a;yum命令报错 “ Cannot find a valid baseurl for repo: base/7/x86_6 ”_centos linux yum search ifconfig cannot find a val-CSDN博客 Centos7出现问题Cannot find a valid baseurl for repo: base/7/x86_64&…

88个群智能算法优化BP神经网络 多特征输入单输出回归预测Matlab程序

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、BP神经网络原理二、优化BP神经网络初始权重过程三、程序内容3.1 88个优化算法清单3.2 实验数据3.3 实验结果 代码获取 前言 在Matlab中优化神经网络的初始权…

图论模型-迪杰斯特拉算法和贝尔曼福特算法★★★★

该博客为个人学习清风建模的学习笔记&#xff0c;部分课程可以在B站&#xff1a;【强烈推荐】清风&#xff1a;数学建模算法、编程和写作培训的视频课程以及Matlab等软件教学_哔哩哔哩_bilibili 目录 ​1图论基础 1.1概念 1.2在线绘图 1.2.1网站 1.2.2MATLAB 1.3无向图的…

【毕业论文】| 基于Unity3D引擎的冒险游戏的设计与实现

&#x1f4e2;博客主页&#xff1a;肩匣与橘 &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01; &#x1f4e2;本文由肩匣与橘编写&#xff0c;首发于CSDN&#x1f649; &#x1f4e2;生活依旧是美好而又温柔的&#xff0c;你也…

学生成绩管理系统(C语言)

系统分析 1. 主菜单的实现 2. 增加人员功能的实现 3. 删除数据功能的实现 4. 编辑人员功能的实现 5. 排序功能的实现 6. 输出功能 7. 查找信息功能 具体代码 #include <stdio.h> #include <string.h> #include <stdlib.h> #define SIZE 100000typedef struc…

level 6 day2-3 网络基础2---TCP编程

1.socket&#xff08;三种套接字&#xff1a;认真看&#xff09; 套接字就是在这个应用空间和内核空间的一个接口&#xff0c;如下图 原始套接字可以从应用层直接访问到网络层&#xff0c;跳过了传输层&#xff0c;比如在ubtan里面直接ping 一个ip地址,他没有经过TCP或者UDP的数…

MVCC数据库并发控制技术

一、引言 MVCC&#xff08;Multi-Version Concurrency Control&#xff09;是一种广泛使用的数据库并发控制技术&#xff0c;它允许数据库读操作和写操作并发执行&#xff0c;而无需加锁整个表或行&#xff0c;从而大大提高了数据库的并发性能和吞吐量。MVCC主要被应用于支持事…

最新全新UI异次元荔枝V4.4自动发卡系统源码

简介&#xff1a; 最新全新UI异次元荔枝V4.4自动发卡系统源码 更新日志&#xff1a; 1增加主站货源系统 2支持分站自定义支付接口 3目前插件大部分免费 4UI页面全面更新 5分站可支持对接其他分站产品 6分站客服可自定义 7支持限定优惠 图片&#xff1a; 会员中心截图&…

docker默认存储地址 var/lib/docker 满了,换个存储地址操作流程

1. 查看docker 存储地址 docker info如下 var/lib/docker2、查看内存大小 按需执行 df -h 找超过100M的大文件 find / -type f -size 100M -exec ls -lh {} \; df -Th /var/lib/docker 查找这个文件的容量 df -h 查找所有挂载点 du -hs /home/syy_temp/*1、df -h 2、sud…

Java中锁的全面详解(深刻理解各种锁)

一.Monitor 1. Java对象头 以32位虚拟机位例 对于普通对象,其对象头的存储结构为 总长为64位,也就是8个字节, 存在两个部分 Kclass Word: 其实也就是表示我们这个对象属于什么类型,也就是哪个类的对象.而对于Mark Word.查看一下它的结构存储 64位虚拟机中 而对于数组对象,我…

卡片式组件封装demo

效果视频&#xff1a; 卡片组件 样式还得细调~&#xff0c;时间有限&#xff0c;主要记录一下逻辑。 html结构&#xff1a; 目录 父组件数据处理数据格式 父组件的全部代码 子组件数据处理props参数 样式部分三个圆点点击三圆点在对应位置显示查看弹框点击非内容部分隐藏查看…

从千台到十万台,浪潮信息InManage V7解锁智能运维密码

随着大模型技术的深度渗透&#xff0c;金融行业正经历着前所未有的智能化变革。从“投顾助手”精准导航投资蓝海&#xff0c;到“智能客服”秒速响应客户需求&#xff0c;大模型以其对海量金融数据的深度挖掘与高效利用&#xff0c;正显著提升金融服务的智能化水准&#xff0c;…