当前位置: 首页 > news >正文

53. 最大子数组和(力扣LeetCode)

文章目录

  • 53. 最大子数组和
    • 题目描述
    • 暴力(运行超时)
    • 贪心

53. 最大子数组和

题目描述

给你一个整数数组 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

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

暴力(运行超时)

// 引入必要的头文件
class Solution {
public:// maxSubArray函数接受一个整数型向量nums作为参数,并返回一个整数int maxSubArray(vector<int>& nums) {// 初始化max为INT_MIN,这表示最小可能的整数,确保任何元素的和都会大于它int max=INT_MIN;// 外层循环遍历数组的每个元素,作为子数组的起点for(int i=0;i<nums.size();i++){// 初始化num为0,它将用来存储从索引i开始的子数组的和int num=0;// 内层循环从i开始遍历数组,每次循环都会增加子数组的长度for(int j=i;j<nums.size();j++){// 将当前元素累加到num上num+=nums[j];// 如果当前的num大于已知的最大值max,就更新maxif(max<num)max=num;}}// 循环结束后,max就是所有子数组和的最大值,返回这个值return max;}
};

这段代码使用了简单直观的暴力方法来求解问题,即尝试数组中所有可能的子数组,并记录下具有最大和的值。这个方法的时间复杂度是O(n^2),因为它使用了两层嵌套循环来遍历所有可能的子数组。这种方法在数组长度非常大时可能会非常慢,但对于较小的数组,它是足够工作的。

贪心

// 包含必要的头文件
#include<vector>
#include<climits> // 用于INT_MIN,代表最小可能的整数
using namespace std;// 定义Solution类,此类包含解决问题的方法
class Solution {
public:// maxSubArray方法接收一个引用传递的整数向量nums,并返回一个整数int maxSubArray(vector<int>& nums) {// 初始化max为INT_MIN,它将记录目前为止遇到的最大子数组和int max=INT_MIN;// 初始化count为0,它将用来计算当前考虑的子数组的和int count=0;// 遍历数组中的每个元素for(int i=0;i<nums.size();i++){// 将当前元素加到count上count+=nums[i];// 如果count大于max,则更新max为count的值if(max<count) max=count;// 如果count小于0,则重置count为0,因为任何包含负和前缀的子数组都不可能构成最大子数组if(count<0) count=0;}// 遍历完成后,max将包含最大子数组和,返回这个值return max;}
};

如果当前子数组和变为负数,那么它不会对结果有帮助,因此将其重置为0。这个实现假定数组中至少有一个正数,这是因为max的初始值是INT_MIN,即使数组中所有数字都是负数,算法也会返回最大的负数。

这个算法的优点是空间复杂度低,因为它只使用了常数空间,并且时间复杂度为O(n),适用于解决大型数组的最大子数组和问题。

相关文章:

53. 最大子数组和(力扣LeetCode)

文章目录 53. 最大子数组和题目描述暴力&#xff08;运行超时&#xff09;贪心 53. 最大子数组和 题目描述 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和。 子数组是数组…...

如何远程SSH连接在家的服务器主机

当您需要通过SSH远程连接到家里的服务器主机时&#xff0c;以下是更详细的实施步骤&#xff1a; 1. 确保服务器主机已开启SSH服务 安装SSH服务&#xff1a;首先&#xff0c;确保您的服务器主机上安装了SSH服务。根据您的操作系统&#xff0c;您可以使用相应的包管理器来安装。…...

【亲测有效】解决三月八号ChatGPT 发消息无响应!

背景 今天忽然发现 ChatGPT 无法发送消息&#xff0c;能查看历史对话&#xff0c;但是无法发送消息。 可能的原因 出现这个问题的各位&#xff0c;应该都是点击登录后顶部弹窗邀请 [加入多语言 alapha 测试] 了&#xff0c;并且语言选择了中文&#xff0c;抓包看到 ab.chatg…...

vue结合vue-electron创建应用程序

这里写自定义目录标题 安装electron第一种方式&#xff1a;vue init electron-vue第二种方式&#xff1a;vue add electron-builder 启动electron调试功能&#xff1a;background操作和使用1、覆盖窗口的菜单上下文、右键菜单2、监听关闭事件、阻止默认行为3、创建悬浮窗口4、窗…...

【C++】STL(二) string容器

一、string基本概念 1、本质 string是C风格的字符串&#xff0c;而string本质上是一个类 string和char * 区别&#xff1a; char * 是一个指针 string是一个类&#xff0c;类内部封装了char*&#xff0c;管理这个字符串&#xff0c;是一个char*型的容器。 2、特点 1、stri…...

PyCM:Python中的混淆矩阵库

PyCM&#xff1a;Python中的混淆矩阵库 在机器学习和数据科学领域&#xff0c;评估模型的性能是至关重要的。混淆矩阵是一种常用的评估工具&#xff0c;用于可视化和量化分类模型的预测结果。PyCM是一个开源的Python库&#xff0c;提供了丰富的功能来计算和分析混淆矩阵。本文将…...

Day22:安全开发-PHP应用留言板功能超全局变量数据库操作第三方插件引用

目录 开发环境 数据导入-mysql架构&库表列 数据库操作-mysqli函数&增删改查 数据接收输出-html混编&超全局变量 第三方插件引用-js传参&函数对象调用 完整源码 思维导图 PHP知识点&#xff1a; 功能&#xff1a;新闻列表&#xff0c;会员中心&#xff0…...

IOS面试题object-c 61-70

61. 阐述isKindOfClass、isMemberOfClass、selector作用分别是什么&#xff1f;isKindOfClass&#xff1a;作用是某个对象属于某个类型或者继承自某类型。 isMemberOfClass&#xff1a;某个对象确切属于某个类型。 selector&#xff1a;通过方法名&#xff0c;获取在内存中的函…...

Git指令reset的参数soft、mixed与hard三者之间的区别

主要内容 reset默认不写参数&#xff0c;与使用mixed参数含义一样 为了描述简洁&#xff0c;使用下图说明&#xff1a; #mermaid-svg-LtChquRXlEV1j6og {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-LtChquRXlEV1j…...

RGMII 接口调试

目录 硬件检查 软件检查 调试步骤 硬件检查 硬件工程师检查原理图和PCB&#xff0c;核查RGMII线路连接是否正确&#xff0c;PHY的 TX连接对端 RX&#xff0c;PHY的RX连接对端TX&#xff0c;原理图上以引脚序号引脚名 引脚类型(输入还是输出)逐一核查RGMII接口各个网络&#…...

Ubuntu 24.04 抢先体验换国内源 清华源 阿里源 中科大源 163源

Update 240307:Ubuntu 24.04 LTS 进入功能冻结期 预计4月25日正式发布。 Ubuntu22.04换源 Ubuntu 24.04重要升级daily版本下载换源步骤 (阿里源)清华源中科大源网易163源 Ubuntu 24.04 LTS&#xff0c;代号 「Noble Numbat」&#xff0c;即将与我们见面&#xff01; Canonica…...

软件设计模式:模板方法模式

1. 简介 模板方法模式是一种行为型设计模式&#xff0c;它定义了一个算法的骨架&#xff0c;将一些步骤延迟到子类中实现。这样&#xff0c;可以在不改变算法结构的情况下&#xff0c;重新定义算法中的某些步骤。 2. 使用条件 模板方法模式适用于以下情况&#xff1a; 算法…...

【算法】Hash存储——开放寻址法

模拟散列表 维护一个集合&#xff0c;支持如下几种操作&#xff1a; I x&#xff0c;插入一个整数 x&#xff1b; Q x&#xff0c;询问整数 x是否在集合中出现过&#xff1b; 现在要进行 N次操作&#xff0c;对于每个询问操作输出对应的结果。 输入格式 第一行包含整数 N&am…...

STM32CubeIDE基础学习-STM32CubeIDE软件程序下载方法

STM32CubeIDE基础学习-STM32CubeIDE软件代码下载方法 文章目录 STM32CubeIDE基础学习-STM32CubeIDE软件代码下载方法前言第1章 代码下载第2章 下载器固件更新总结 前言 编写完代码&#xff0c;一般都会选择在线下载程序的方式进行验证该程序是否正确&#xff0c;如果发现结果和…...

LeetCode 174.地下城游戏 Python题解

地下城游戏 # 地下城游戏 """ 恶魔们抓住了公主并将她关在了地下城dungeon的右下角。地下城是由mxn个房间组成的二维网格。我们英勇的骑士最初被安置在左上角的房间里&#xff0c; 他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数…...

指令调用模板

也就是这边指令通过id和map会定位到一个结构体&#xff0c;然后这个结构再赋值两个成员&#xff0c;一个是函数一个是指令类型&#xff0c;然后这个函数是模板的实例化 使用的时候就传进去&#xff0c;这只是参数&#xff0c;最开始初始化的时候模板就已经实例化了。然后关于模…...

(五)关系数据库标准语言SQL

注&#xff1a;课堂讲义使用的数据库 5.1利用SQL语言建立数据库 5.1.1 create Database 5.1.2 create schema...authorization... 创建数据库和创建模式的区别&#xff1a; 数据库是架构的集合&#xff0c;架构是表的集合。但在MySQL中&#xff0c;他们使用的方式是相同的。 …...

第二十天-数据分析

1.介绍 1.什么是数据分析 1.以下4个纬度结合起来的数据科学 2.数据分析的特殊性...

鸿蒙Harmony应用开发—ArkTS声明式开发(通用属性:外描边设置)

设置组件外描边样式。 说明&#xff1a; 从API Version 11开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 outline outline(value: OutlineOptions) 统一外描边样式设置接口。 卡片能力&#xff1a; 从API version 11开始&#xff0c;该…...

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:CalendarPicker)

日历选择器组件&#xff0c;提供下拉日历弹窗&#xff0c;可以让用户选择日期。 说明&#xff1a; 该组件从API Version 10开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 无 接口 CalendarPicker(options?: CalendarOptions) …...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...