【状态机DP】力扣1186. 删除一次得到子数组最大和

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

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

示例 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 {
public:int maximumSum(vector<int>& arr) {int n = arr.size(), res = arr[0];vector<vector<int>> dp(n, vector<int>(2));dp[0][0] = arr[0], dp[0][1] = 0;for(int i = 1; i < n; i++){dp[i][0] = max(dp[i-1][0], 0) + arr[i];dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i]);res = max(res, max(dp[i][0], dp[i][1]));}   return res;}
};

时间复杂度:O(n),其中 n 是数组 arr 的长度。
空间复杂度:O(n)。

我们定义一个动态规划数组dp,dp[i][0]代表以arr[i]结尾的子数组,并且没有删除过元素,dp[i][1]代表以arr[i]结尾的子数组,并且删除过元素。

所以我们有状态转移方程dp[i][0] = max(dp[i-1][0], 0) + arr[i]; dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i]);,并且在计算第一个状态转移方程的时候,需要使用max操作是因为如果dp[i-1][0]是负数,则重新从0开始计算。

有人会问,那么你在dp[i][0]中使用max操作,为什么不在dp[i][1]的状态转移方程中使用max(dp[i-1][1], 0) + arr[i]呢,因为我们在之前dp[i][0]中如果前面dp[i-1][0]为负数,则以arr[i]重新开始计算,但是由于现在的dp[i][1]要求必须删除一个元素,那么不可能从arr[i]开始算起,但是没有删除任何元素。

最后res记录每一种可能的情况的最大值。

class Solution {
public:int maximumSum(vector<int>& arr) {int n = arr.size(), res = arr[0];int dp0 = arr[0], dp1 = 0;for(int i = 1; i < n; i++){dp1 = max(dp0, dp1 + arr[i]);dp0 = max(dp0, 0) + arr[i];res = max(res, max(dp0, dp1));}   return res;}
};

时间复杂度:O(n),其中 n 是数组 arr 的长度。
空间复杂度:O(1)。

我们可以通过滚动数组的方式进行优化,并且我们可以发现dp1由之前的dp0状态转换而来,而dp0由自身之前的状态转换而来,如果按之前顺序dp0后dp1则dp0会进行覆盖,从而影响dp1的运算,所以我们先计算dp1后计算dp0。

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

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

相关文章

手机拍证件照,换正装有领衣服及底色的方法

证件照在我们的职业生涯的关键节点是经常会用到的&#xff0c;比如毕业入职、人事档案建立、升迁履历、执业资格考试和领证等&#xff0c;这些重要的证件照往往要求使用正装照&#xff0c;有时候手头没有合适的衣服&#xff0c;或者原先的证件照背景色不符合要求&#xff0c;就…

numpy——数学运算

一、标量——矢量 import numpy as npa 3.14 b np.array([[9, 5], [2, 7]])print(a) print(b)# ---------- 四则运算 ---------- print(a b) # np.add print(a - b) # np.subtract print(a * b) # np.multiply print(a / b) # np.divide 二、矢量——矢量 import nump…

优选算法精品课--双指针算法(2)

双指针算法&#xff08;2&#xff09; 1、有效三角形的个数1.1 题目解析1.2 思路解析1.3 代码实现 2、和为s的两个数2.1 题目解析2.2 思路解析2.3 代码实现 3、三数之和3.1 题目解析3.2 思路解析3.3 代码实现 4、四数之和4.1 题目解析4.2 思路解析4.3 代码实现 5 总结 1、有效三…

4个提取音频办法,轻松实现视频转音频!

在信息爆炸的时代&#xff0c;视频内容以其直观、生动的特点占据了互联网的大半江山。然而&#xff0c;在某些场景下&#xff0c;我们可能更倾向于只听取音频部分&#xff0c;无论是驾驶途中听讲座、跑步时享受音乐视频中的纯音乐的场景&#xff0c;还是为了节省流量和存储空间…

Python continue和break

continue的作用是&#xff1a; 中断所在循环的当次执行&#xff0c;直接进入下一次 break的作用是&#xff1a; 直接结束所在的循环 注意事项&#xff1a; continue和break&#xff0c;在for和while循环中作用一致 在嵌套循环中&#xff0c;只能作用在所在的循环上&#x…

【01初识】-初识 RabbitMQ

目录 学习背景1- 初识 MQ1-1 同步调用什么是同步调用&#xff1f;小结&#xff1a;同步调用优缺点 1-2 异步调用什么是异步调用&#xff1f;小结&#xff1a;异步调用的优缺点&#xff0c;什么时候使用异步调用&#xff1f; 1-3 MQ 技术选型 学习背景 异步通讯的特点&#xff…

300元蓝牙耳机性价比高的有哪些?学生平价蓝牙耳机推荐

你是否正在为选择一款性价比高的蓝牙耳机而烦恼&#xff1f;是否希望找到一款既适合学生使用&#xff0c;又能在预算内满足需求的蓝牙耳机&#xff1f;300元蓝牙耳机性价比高的有哪些&#xff1f;如果你有这样的需求&#xff0c;那么下面我将为大家提供一些有益的参考&#xff…

中间件安全(三)

本文仅作为学习参考使用&#xff0c;本文作者对任何使用本文进行渗透攻击破坏不负任何责任。 前言: 本文主要讲解apache命令执行漏洞&#xff08;cve_2021_41773&#xff09;。 靶场链接&#xff1a;Vulfocus 漏洞威胁分析平台 一&#xff0c;漏洞简介。 cve_2021_41773漏洞…

【STM32外设及其应用】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

pyvideotrans 最佳AI翻译软件

文章目录 体验视频翻译配音工具主要用途和功能预打包版本(仅win10/win11可用&#xff0c;MacOS/Linux系统使用源码部署)MacOS源码部署Linux 源码部署Window10/11 源码部署源码部署问题说明使用教程和文档语音识别模型:视频教程(第三方)软件预览截图相关联项目致谢 体验 不错&a…

【含开题报告+文档+PPT+源码】基于SpringBoot的健康知识学习分享平台的设计与实现

开题报告 随着人们生活水平的提高和健康意识的增强&#xff0c;健康知识在日常生活中的重要性日益凸显。传统的健康知识获取途径如书籍、讲座等虽然具有一定的效果&#xff0c;但存在信息更新慢、交互性差等局限性。同时&#xff0c;互联网的普及和移动互联网的发展为人们提供…

【算法刷题指南】双指针

&#x1f308;个人主页&#xff1a; 南桥几晴秋 &#x1f308;C专栏&#xff1a; 南桥谈C &#x1f308;C语言专栏&#xff1a; C语言学习系列 &#x1f308;Linux学习专栏&#xff1a; 南桥谈Linux &#x1f308;数据结构学习专栏&#xff1a; 数据结构杂谈 &#x1f308;数据…

前端零基础入门到上班:【Day1】什么是前端?

本来打算开付费专栏 但是想起那句话 赠人玫瑰手留余香 引言1. 什么是前端&#xff1f;1.1 前端的定义1.2 前端的三大核心技术1.3 前端框架和工具 2. 什么是后端&#xff1f;2.1 后端的定义2.2 后端的组成要素2.3 后端框架和工具 3. 前后端的区别4. 什么是前后端分离&#xff1f…

院士领衔,瑞德磁电誓将中国红染遍磁电产业

【哔哥哔特导读】今天我们从广州来到淮北&#xff0c;参观一家由院士领衔创立的金属磁粉芯企业&#xff0c;看他们如何将中国红染遍磁电产业&#xff0c;一步步实现金属磁粉芯的国产替代。 想要成为一个领域的头部企业&#xff0c;技术实力与产能规模缺一不可&#xff0c;而瑞…

[翱捷]让SDK跑起来了

一&#xff0c;环境安排及验证 参照文档 <<ASR编译环境及编译步骤--3601.docx>> <<Windows环境搭建.docx>> <<ChildWatchSWUG_1221.doc>> 主要工具包括 ARM DS-5 V5.26.2 (64-bit)ActivePerl 5.28.1 Build 2801 (64-bit)msys2-x86_6…

摊牌了,创业失败了

“以为这个网红不会塌房&#xff0c;结果一觉醒来&#xff0c;天塌了……” ——某电商供应商 “这不是禁不住网上的各种诱惑吗&#xff0c;9月30日纵身入局&#xff0c;节假日几天不能买入&#xff0c;8号上班第一天我还看着钱数开心呢。结果今天……” ——一位投资失利&…

Python日志系统详解:Logging模块最佳实践

Python日志系统详解&#xff1a;Logging模块最佳实践 在开发Python应用程序时&#xff0c;日志记录是排查问题、监控系统状态、优化性能的重要手段。Python标准库中提供了强大的logging模块&#xff0c;使开发者可以轻松实现灵活的日志系统。本文将详细介绍Python的logging模块…

Java实现邮箱发送邮件添加定时任务(二)

上篇文章我们谈到邮件的发送&#xff0c;但是可以发现使用非常局限&#xff0c;这里我做了一个简单的修改&#xff0c;添加了定时发送功能&#xff0c;可以帮助我们处理很多繁琐的事 这里我写了一个简单的案例 1. 先在pom文件里面添加依赖 2.配置yml文件 3.写一个定时任务类…

python项目实战——多协程下载美女图片

协程 文章目录 协程协程的优劣势什么是IO密集型任务特点示例与 CPU 密集型任务的对比处理 I/O 密集型任务的方式总结 创建并使用协程asyncio模块 创建协程函数运行协程函数asyncio.run(main())aiohttp模块调用aiohttp模块步骤 aiofiles————协程异步函数遇到的问题一 await …

AI最新动态概览-2024年10月28日

1. 字节跳动加速欧洲布局&#xff0c;拟建AI研发中心 近日&#xff0c;有消息称字节跳动正积极筹备在欧洲设立AI研发中心&#xff0c;此举标志着该公司在全球技术版图上的又一重要扩张。随着人工智能技术的飞速发展&#xff0c;字节跳动正通过招兵买马&#xff0c;进一步巩固其…