(动态规划,分治)leetcode53. 最大子数组和

news/2024/4/15 11:02:22

文章目录

  • 一、题目
    • 1、题目描述
    • 2、基础框架
    • 3、原题链接
  • 二、解题报告
    • 1、思路分析
    • 2、时间复杂度
    • 3、代码详解
  • 三、本题小知识

一、题目

1、题目描述

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:
输入:nums = [1]
输出:1

示例 3:
输入:nums = [5,4,-1,7,8]
输出:23

2、基础框架

  • C++版本给出的基础框架如下:

3、原题链接

https://leetcode.cn/problems/maximum-subarray/

二、解题报告

1、思路分析

   ( 1 ) (1) (1)采用动态规划的思路,dp[i]表示以下标i为右边界的子数组的最大值,dp[i]只跟dp[i-1]有关,如果dp[i-1] + nums[i] > nums[i]。那么dp[i]的最大值为dp[i-1]+nums[i],否则为nums[i].
   ( 2 ) (2) (2)dp中的最大值即为最大连续子数组和。

2、时间复杂度

时间复杂度为O(n),空间复杂度为O(n)

3、代码详解

class Solution {
public:int maxSubArray(vector<int>& nums) {vector<int> dp(nums.size());int re = nums[0];for (int i = 0; i < nums.size(); i++) {dp[i] = nums[i];re = max(re, dp[i]);}for (int i = 1; i < nums.size(); i++) {if (dp[i] + dp[i-1] >= dp[i]) {dp[i] = dp[i] + dp[i-1];re = max(re, dp[i]);}}return re;}
};

三、本题小知识


http://www.ppmy.cn/news/68092.html

相关文章

android room数据库简单使用

Room来源 Android采用Sqlite作为数据库存储。由于Sqlite代码写起来繁琐且容易出错&#xff0c;因此&#xff0c;开源社区逐渐出现了各种ORM&#xff08;Object Relational Mapping&#xff09;库。常见的有ORMLite, GreenDAO等。Google也意识到推出自家ORM库的必要性&#xff0…

什么是VLAN?为什么要划分VLAN?

VLAN(Virtual Local Area Network)即虚拟局域网&#xff0c;是将一个物理的LAN在逻辑上划分成多个广播域的通信技术。每个VLAN是一个广播域&#xff0c;VLAN内的主机间可以直接通信&#xff0c;而VLAN间则不能直接互通。这样&#xff0c;广播报文就被限制在一个VLAN内。 一、为…

蓝桥杯模块学习3——蜂鸣器与继电器

第一章 硬件部分 1.1 电路的组成部分 1.1.1 译码器和锁存器 具体可回顾之前LED灯的文章&#xff1a; https://blog.csdn.net/weixin_63568691/article/details/130660096 1.1.2 ULN2003达林顿管 原理图&#xff1a; 功能&#xff1a; &#xff08;1&#xff09;改变电路特性…

栈和队列的实现

栈 栈的概念 栈也是线性表的一种&#xff0c;但是栈只允许在固定的一端进行插入与删除数据&#xff0c;而进行插入与删除的一端同意称为栈顶&#xff0c;而另一端就称为栈底。简称&#xff1a;后进先出。 压栈&#xff08;push&#xff09;&#xff1a;将数据插入栈顶。 出…

ANR实战案例 2 - 不同线程状态ANR示例

系列文章目录 提示&#xff1a;这里可以添加系列文章的所有文章的目录&#xff0c;目录需要自己手动添加 例如&#xff1a;第一章 Python 机器学习入门之pandas的使用 文章目录 系列文章目录前言一、Blocked状态示例1.启动初始化阻塞案例trace1.tx 2.ConcurrentHashMap分段锁优…

SwiftUI 4.0 中 List 显示层级数据的子视图在展开和收起操作时无动画的解决

问题现象 在 SwiftUI 4.0(iOS 16+)中,一个超简单 List 视图层级子视图的收放操作竟然没有动画,这着实有点让人不爽: 从上图可以看到:我们在点击 List 子项时不仅毫无收放动画可言,而且在展开时还有卡顿,显得非常生硬。 以上代码在目前最新的 iOS 16.4.1(a) 系统中测试…

非常提效的7款原型工具推荐

原型图工具允许在开发前进行测试和迭代过程&#xff0c;可以帮助节省大量的开发时间和成本。在本文中&#xff0c;我们盘点了7个易于使用的原型图工具&#xff0c;以提高您的生产力&#xff01; 1.即时设计 即时设计是一款免费的在线 UI 设计工具&#xff0c;无系统限制&…

Rust Atomics and Locks 阅读笔记 第二章 Atomics

原子操作&#xff08;atomic operations&#xff09;是多线程实现的基石&#xff0c;互斥锁&#xff08;mutex&#xff09;和条件变量&#xff08;condition variable&#xff09;都是通过原子操作来实现&#xff1b;std::sync::atomic包括了rust的内置原子操作类型&#xff08…

【C++入门编程常见问题】(小白必看)

常见问题 vsstudio快捷键 快速注释组合键 ctrlk ctrlc 取消注释快捷键 ctrlk ctrl u 支持垃圾回收机制 大多数面向对象编程语言具有垃圾回收机制。早期的C语言不具备垃圾回收机制&#xff0c;这意味着申请的内存资源在使用完成后&#xff0c;需要程序员自己释放。直到C11标…

搞懂 MyBatis 的事务管理机制

MyBatis 是一款优秀的持久层框架&#xff0c;相信很多 Java 后端开发人员对它都不会陌生。在实际项目开发中&#xff0c;事务管理是非常重要的一环&#xff0c;而 MyBatis 也为我们提供了便捷的事务管理机制。 本文将从以下方面详细解析 MyBatis 的事务管理机制&#xff1a; …

三十二、自定义镜像

1 、Docker镜像的原理 Docker镜像本质是什么? Docker中一个centos镜像为什么只有200MB&#xff0c;而一个centos操作系统的iso文件要几个G? Docker中一个tomcat镜像为什么有500MB&#xff0c;而一个tomcat安装包只有10多MB? 操作系统组成部分: 计算机组成原理 进程调度子…

Java项目中常用的SON转换方式及示例

摘要: JSON&#xff08;JavaScript Object Notation&#xff09;是一种常用的数据交换格式&#xff0c;用于在不同的应用程序之间传输和存储数据。在Java开发中&#xff0c;我们经常需要将Java对象转换为JSON格式&#xff0c;或者将JSON转换回Java对象。本文将介绍几种常见的JS…

卫龙上市后首份财报:营收净利双降、去年净利下滑8成

当你吃辣条的时候&#xff0c;你在吃什么&#xff1f; 味道&#xff1f;口感&#xff1f;还是童年的记忆&#xff1f; 近日&#xff0c;卫龙美味全球控股有限公司&#xff08;下称“卫龙”&#xff09;发布了上市后的首份年报。 卫龙是一家辣味休闲食品的企业&#xff0c;根…

如何在 Mac 或 Windows 上将 PDF 转换为 Word 而不丢失格式

PDF 有无数的优点&#xff0c;但它不能像 Microsoft Word 文档那样容易编辑。如果您没有价格总是很高的 PDF 编辑器&#xff0c;您将无法根据需要编辑或使用 PDF 源。但是我们可以将PDF转成Word&#xff0c;方便编辑。 有很多解决方案可用于在 Mac 上将 PDF 转换为可编辑的 W…

〖Web全栈开发①〗—网络编程基础(上)

网络编程基础 网络编程网络编程概述TCP/IP协议IP地址什么是IPIP组成IP 地址使用过程查看IPIp地址分类&#xff1a;子网掩码 端口 socketSocket原理&#xff11;.什么是Socket2.创建一个tcp socket&#xff08;tcp套接字&#xff09; tcp 介绍 &#x1f3d8;️&#x1f3d8;️个…

awk命令编辑

awk工作原理 逐行读取文本&#xff0c;默认以空格或tab键分隔符进行分隔&#xff0c;将分隔所得的各个字段保存到内建变量中&#xff0c;并按模式或者条件执行编辑命令。 sed命令常用于一整行的处理&#xff0c;而awk比较倾向于将一行分成多个“字段”然后再进行处理。awk信息…

WINCC和EXCEL的OPC通讯

Option Explicit Option Base 1 Const ServerName “OPCServer.WinCC” Dim WithEvents MyOPCServer As OpcServer Dim WithEvents MyOPCGroup As OPCGroup Dim MyOPCGroupColl As OPCGroups Dim MyOPCItemColl As OPCItems Dim MyOPCItems As OPCItems Dim MyOPCItem As OPCI…

我的服务器被挖矿了,原因竟是。。。

「作者简介」&#xff1a;CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」&#xff1a;对网络安全感兴趣的小伙伴可以关注专栏《网络安全入门到精通》 挖矿木马应急响应 一、什么是挖矿二、被挖矿主机现象三、挖矿木马处置思路1&#xff09;隔…

【Linux】RK3399平台开发系列——设备树的学习笔记

学习内容 RK3399平台开发系列讲解&#xff08;设备树篇&#xff09;设备树的详解 - 视频介绍 简介 设备树&#xff08;Device Tree&#xff09;是用于描述硬件设备和系统关系的树形数据结构&#xff0c;主要用于 Linux 操作系统中的设备驱动程序。在嵌入式系统中&#xff0c…

如何通过品牌矩阵号赋能品牌?

小红书作为年轻人的“消费决策”平台、逐步成为越来越多用户的消费指南&#xff0c;同时也变成众多品牌的营销基地。在小红书运营矩阵账号可以很好的树立品牌形象、增加粉丝粘性、节约广告成本&#xff0c;那么在搭建矩阵的过程中如何管理品牌矩阵号也成为众多品牌必须要思考的…
最新文章