leetcode(动态规划)53.最大子数组和(C++详细解释)DAY12

文章目录

  • 1.题目
    • 示例
    • 提示
  • 2.解答思路
  • 3.实现代码
    • 结果
  • 4.总结

1.题目

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

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

示例

在这里插入图片描述

提示

在这里插入图片描述

2.解答思路

起初思路暴力求解,两层for循环,但超出时间限制。
查看其他题解,学习以下动态规划算法。
关于动态规划算法,后续会出一篇文章详细解释。
此处简述:
动态规划的核心思想是将原始问题分解为更小的子问题,并通过求解子问题的解来推导出原始问题的解。避免重复计算,提高算法的效率。

3.实现代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum=nums[0];
        int n=nums.size();

        int sum=nums[0];//记录当下的和

        for(size_t i=1;i<n;++i){
            sum += nums[i];
            sum = max(sum,nums[i]);
            /*
            将当下及之前元素的和max和单个元素进行比较nums[i],求最大值
            若当下的和 大于 单个元素,则加和运算
            若当下的和 小于 单个元素,则将单个元素的值赋给max,
            以便后续继续求解*/
            maxSum=max(sum,maxSum);         
        }


        return maxSum;
    }
};

结果

在这里插入图片描述
暴力求解一直超时。
动态规划算法将时间复杂度降到了O(n),通过。

4.总结

前两天感冒突然严重+家中亲人走访,学习时间减少,今天病情好转,后续会继续更新学习。

自信,坚持,upup~

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

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

相关文章

数论 - 博弈论(Nim游戏)

文章目录 前言一、Nim游戏1.题目描述输入格式输出格式数据范围输入样例&#xff1a;输出样例&#xff1a; 2.算法 二、台阶-Nim游戏1.题目描述输入格式输出格式数据范围输入样例&#xff1a;输出样例&#xff1a; 2.算法 三、集合-Nim游戏1.题目描述输入格式输出格式数据范围输…

vue使用Nprogress进度条功能实现

下图中的这种顶部进度条是非常常见的&#xff0c;在vue项目中有对应的插件&#xff1a;Nprogress。 实现效果&#xff1a; csdn也在使用&#xff1a; 或者这样自己使用 1、安装 NProgress可以通过npm安装。 npm install --save nprogress 注意此处的--save等同于-s,就是将…

echats 时间直方图示例

需求背景 某订单有N个定时任务&#xff0c;每个任务的执行时间已经确定&#xff0c;希望直观的查看该订单的任务执行趋势 查询SQL&#xff1a; select UNIX_TIMESTAMP(DATE_FORMAT(exec_time,%Y-%m-%d %H:%i)) execTime, count(*) from order_detail_task where order_no 2…

【C++】vector模拟实现+迭代器失效

vector模拟实现 成员变量定义默认成员函数构造函数 迭代器范围for、对象类型匹配原则 容量操作sizeemptycapacityreserve成员变量未更新memcpy值拷贝 resize内置类型的构造函数 数据访问frontbackoperator[ ] 数据修改操作push_backpop_backswapclearinsertpos位置未更新无返回…

el-button 选择与非选择按钮批量处理

el-button 选择与非选择按钮批量处理 <el-button v-for"(voyage,i) in data[voyages][nowVoyage]":key"i"class"c-work-bts"type"primary":plain"nowWorkSpace!i"click"chooseWorkSpace(i)"size"small&qu…

C#快速配置NLog日志使用

首先我们需要在Nuget中安装Nlog和Nlog-Schema。 添加配置文件&#xff1a;NLog.config <?xml version"1.0" encoding"utf-8" ?> <nlog xmlns"http://www.nlog-project.org/schemas/NLog.xsd"xmlns:xsi"http://www.w3.org/2001…

CSS弹性布局

CSS弹性布局 一、概念 ​ 弹性盒子是 CSS3 的一种新的布局模式。 ​ CSS3 弹性盒&#xff08; Flexible Box 或 flexbox&#xff09;&#xff0c;是一种当页面需要适应不同的屏幕大小以及设备类型时确保元素拥有恰当的行为的布局方式。 ​ 引入弹性盒布局模型的目的是提供一…

山西电力市场日前价格预测【2024-02-21】

日前价格预测 预测说明&#xff1a; 如上图所示&#xff0c;预测明日&#xff08;2024-02-21&#xff09;山西电力市场全天平均日前电价为470.29元/MWh。其中&#xff0c;最高日前电价为654.81元/MWh&#xff0c;预计出现在18:45。最低日前电价为355.63元/MWh&#xff0c;预计…

将Windows的系统日志自动收集并且转发到syslog服务器,百试百灵

将windows的系统日志自动收集并且转发到syslog服务器&#xff0c;百试百灵* **使用*Evtsys工具&#xff0c;他会自动收集windows系统日志&#xff0c;然后发送到syslog服务器&#xff0c;并且不乱码 下载链接&#xff1a;百度云永久链接 链接&#xff1a;https://pan.baidu.co…

D9741——用于也收路像机和笔记本电的等设备上的直流转换器。在便携式的仪器设备上。低电压输入时误操作保护电路, 定时闩锁、短路保护电路等功能

D9741是一块脉宽调制方三用于也收路像机和笔记本电的等设备上的直流转换器。在便携式的仪器设备上。 主要特点: 高精度基准电路 定时门锁、短路保护电路 低电压输入时误操作保护电路 输出基准电压(2.5V 超过工作范围能进行自动校正 封装形式: SOP16 应用: 电视摄像机 笔记本电…

5个顶级开源法学硕士大型语言模型 (LLM)

5个顶级开源法学硕士大型语言模型 (LLM)。 在快速发展的人工智能 (AI) 世界中&#xff0c;大型语言模型 (LLM) 已成为推动创新并重塑我们与技术交互方式的基石。 随着这些模型变得越来越复杂&#xff0c;人们越来越重视对它们的访问的民主化。 尤其是开源模型&#xff0c;在这…

算法面试八股文『 模型详解篇 』

说在前面 这是本系列的第二篇博客&#xff0c;主要是整理了一些经典模型的原理和结构&#xff0c;面试有时候也会问到这些模型的细节&#xff0c;因此都是需要十分熟悉的。光看原理还不够&#xff0c;最好是能用代码试着复现&#xff0c;可以看看李沐老师深度学习的教材&#…

线程池:优化多线程管理的利器

引言 同步和异步想必各位都有了解&#xff0c;同步简单来说就是一件事做完再去做下一件&#xff1b;异步则是不用等一件事做完&#xff0c;就可以去做另一件事&#xff0c;当一件事完成后可以收到对应的通知&#xff1b;异步一般应用于一些耗时较长的操作&#xff0c;比如大型…

量子计算:数据安全难题

当今数字技术面临的最大挑战之一是安全系统和数据。为此&#xff0c;人们设计了复杂的算法来加密数据并通过称为对称加密的框架来保护数据。虽然这已被证明是成功的&#xff0c;但量子计算的进步&#xff08;利用量子力学比传统计算机更快地解决复杂问题&#xff09;可能会彻底…

Flink的单元测试介绍及示例

本文详细的介绍了Flink的单元测试&#xff0c;分为有状态、无状态以及作业的测试&#xff0c;特别是针对无状态的单元测试给出了常见的使用示例。 本文除了maven依赖外&#xff0c;没有其他依赖。 一、Flink测试概述 Apache Flink 同样提供了在测试金字塔的多个级别上测试应用程…

离谱,华为食堂也要搞末位淘汰

华为饭堂 末位淘汰 今天逛职场 App&#xff0c;无意间翻到一篇帖子&#xff1a; 点开图片之前&#xff0c;我还以为只是普通的争霸赛被网友解读为末位淘汰。 点开图片后我却发现 ... 可以看出&#xff0c;是深圳华为的行政部做的海报&#xff0c;里面清晰写到&#xff1a;员工的…

QT-地形3D

QT-地形3D 一、 演示效果二、关键程序三、下载链接 一、 演示效果 二、关键程序 #include "ShaderProgram.h"namespace t3d::core {void ShaderProgram::init() {initializeOpenGLFunctions();loadShaders(); }void ShaderProgram::addShader(const QString &fil…

如何使用Docker搭建YesPlayMusic网易云音乐播放器并发布至公网访问

文章目录 1. 安装Docker2. 本地安装部署YesPlayMusic3. 安装cpolar内网穿透4. 固定YesPlayMusic公网地址 本篇文章讲解如何使用Docker搭建YesPlayMusic网易云音乐播放器&#xff0c;并且结合cpolar内网穿透实现公网访问音乐播放器。 YesPlayMusic是一款优秀的个人音乐播放器&am…

JS逆向进阶篇【去哪儿旅行登录】【中篇-滑动轨迹破解补浏览器环境破参数】

目录&#xff1a; 每篇前言&#xff1a;0、整体分析1、逆向轨迹snapshot&#xff08;1&#xff09;分析&#xff1a;&#xff08;2&#xff09;Python轨迹生成&#xff1a;&#xff08;3&#xff09;AES加密&#xff1a;&#xff08;4&#xff09;轨迹加密&#xff1a;&#xf…

springcloud:1.Eureka详细讲解

Eureka 是 Netflix 开源的一个服务注册和发现工具,被广泛应用于微服务架构中。作为微服务架构中的核心组件之一,Eureka 提供了服务注册、发现和失效剔除等功能,帮助构建弹性、高可用的分布式系统。在现代软件开发领域,使用 Eureka 可以有效地管理和监控服务实例,实现服务之…