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. 最大子数组和题目描述暴力(运行超时)贪心 53. 最大子数组和 题目描述 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组是数组…...
如何远程SSH连接在家的服务器主机
当您需要通过SSH远程连接到家里的服务器主机时,以下是更详细的实施步骤: 1. 确保服务器主机已开启SSH服务 安装SSH服务:首先,确保您的服务器主机上安装了SSH服务。根据您的操作系统,您可以使用相应的包管理器来安装。…...

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

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

【C++】STL(二) string容器
一、string基本概念 1、本质 string是C风格的字符串,而string本质上是一个类 string和char * 区别: char * 是一个指针 string是一个类,类内部封装了char*,管理这个字符串,是一个char*型的容器。 2、特点 1、stri…...

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

Day22:安全开发-PHP应用留言板功能超全局变量数据库操作第三方插件引用
目录 开发环境 数据导入-mysql架构&库表列 数据库操作-mysqli函数&增删改查 数据接收输出-html混编&超全局变量 第三方插件引用-js传参&函数对象调用 完整源码 思维导图 PHP知识点: 功能:新闻列表,会员中心࿰…...
IOS面试题object-c 61-70
61. 阐述isKindOfClass、isMemberOfClass、selector作用分别是什么?isKindOfClass:作用是某个对象属于某个类型或者继承自某类型。 isMemberOfClass:某个对象确切属于某个类型。 selector:通过方法名,获取在内存中的函…...
Git指令reset的参数soft、mixed与hard三者之间的区别
主要内容 reset默认不写参数,与使用mixed参数含义一样 为了描述简洁,使用下图说明: #mermaid-svg-LtChquRXlEV1j6og {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-LtChquRXlEV1j…...
RGMII 接口调试
目录 硬件检查 软件检查 调试步骤 硬件检查 硬件工程师检查原理图和PCB,核查RGMII线路连接是否正确,PHY的 TX连接对端 RX,PHY的RX连接对端TX,原理图上以引脚序号引脚名 引脚类型(输入还是输出)逐一核查RGMII接口各个网络&#…...

Ubuntu 24.04 抢先体验换国内源 清华源 阿里源 中科大源 163源
Update 240307:Ubuntu 24.04 LTS 进入功能冻结期 预计4月25日正式发布。 Ubuntu22.04换源 Ubuntu 24.04重要升级daily版本下载换源步骤 (阿里源)清华源中科大源网易163源 Ubuntu 24.04 LTS,代号 「Noble Numbat」,即将与我们见面! Canonica…...
软件设计模式:模板方法模式
1. 简介 模板方法模式是一种行为型设计模式,它定义了一个算法的骨架,将一些步骤延迟到子类中实现。这样,可以在不改变算法结构的情况下,重新定义算法中的某些步骤。 2. 使用条件 模板方法模式适用于以下情况: 算法…...

【算法】Hash存储——开放寻址法
模拟散列表 维护一个集合,支持如下几种操作: I x,插入一个整数 x; Q x,询问整数 x是否在集合中出现过; 现在要进行 N次操作,对于每个询问操作输出对应的结果。 输入格式 第一行包含整数 N&am…...

STM32CubeIDE基础学习-STM32CubeIDE软件程序下载方法
STM32CubeIDE基础学习-STM32CubeIDE软件代码下载方法 文章目录 STM32CubeIDE基础学习-STM32CubeIDE软件代码下载方法前言第1章 代码下载第2章 下载器固件更新总结 前言 编写完代码,一般都会选择在线下载程序的方式进行验证该程序是否正确,如果发现结果和…...
LeetCode 174.地下城游戏 Python题解
地下城游戏 # 地下城游戏 """ 恶魔们抓住了公主并将她关在了地下城dungeon的右下角。地下城是由mxn个房间组成的二维网格。我们英勇的骑士最初被安置在左上角的房间里, 他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数…...

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

(五)关系数据库标准语言SQL
注:课堂讲义使用的数据库 5.1利用SQL语言建立数据库 5.1.1 create Database 5.1.2 create schema...authorization... 创建数据库和创建模式的区别: 数据库是架构的集合,架构是表的集合。但在MySQL中,他们使用的方式是相同的。 …...

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

鸿蒙Harmony应用开发—ArkTS声明式开发(通用属性:外描边设置)
设置组件外描边样式。 说明: 从API Version 11开始支持。后续版本如有新增内容,则采用上角标单独标记该内容的起始版本。 outline outline(value: OutlineOptions) 统一外描边样式设置接口。 卡片能力: 从API version 11开始,该…...

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:CalendarPicker)
日历选择器组件,提供下拉日历弹窗,可以让用户选择日期。 说明: 该组件从API Version 10开始支持。后续版本如有新增内容,则采用上角标单独标记该内容的起始版本。 子组件 无 接口 CalendarPicker(options?: CalendarOptions) …...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...

网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...

MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...

Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...