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

C++算法练习day70——53.最大子序和

题目来源:. - 力扣(LeetCode)

题目思路分析

题目:寻找最大子数组和(也称为最大子序和)。

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

思路

  1. 暴力解法:最直接的方法是遍历所有可能的子数组,并计算它们的和,然后找出其中的最大值。然而,这种方法的时间复杂度是 O(n^3),对于大型数组来说效率太低。

  2. 动态规划:我们可以使用动态规划来优化这个问题。定义一个变量 maxnums 来记录当前找到的最大子数组和,另一个变量 pos 来记录当前子数组的和(以当前元素为结尾)。遍历数组时,对于每个元素,我们有两种选择:要么将其加入当前的子数组(即 pos + nums[i]),要么开始一个新的子数组(即 nums[i])。然后,更新 maxnums 为 maxnums 和 pos 中的较大值。

  3. Kadane's Algorithm:上述动态规划方法实际上就是著名的 Kadane's Algorithm。它的核心思想是,在遍历数组时,不断更新以当前元素为结尾的最大子数组和,同时记录全局的最大子数组和。

代码:

#include <vector>  
#include <algorithm> // 为了使用 max 函数  class Solution {  
public:  int maxSubArray(vector<int>& nums) {  // 初始化最大子数组和为数组的第一个元素  int maxnums = nums[0];  // 初始化当前子数组和为数组的第一个元素  int pos = nums[0];  // 遍历数组(从第二个元素开始)  for (int i = 1; i < nums.size(); i++) {  // 更新当前子数组和:要么继续当前子数组,要么开始新的子数组  pos = max(pos + nums[i], nums[i]);  // 更新全局最大子数组和  maxnums = max(maxnums, pos);  }  // 返回全局最大子数组和  return maxnums;  }  
};

知识点摘要

  1. Kadane's Algorithm:一种用于解决最大子数组和问题的线性时间复杂度算法。
  2. 动态规划:一种通过将问题分解为更小的子问题来解决问题的方法,通常用于优化问题。
  3. max 函数:用于比较两个值并返回其中的较大值。

本文介绍了如何使用 Kadane's Algorithm 来解决最大子数组和问题。通过维护两个变量(全局最大子数组和和当前子数组和),我们可以在遍历数组时不断更新它们,并最终得到全局最大子数组和。这种方法的时间复杂度是 O(n),非常高效。希望本文能帮助大家更好地理解最大子数组和问题和 Kadane's Algorithm。

http://www.lryc.cn/news/501410.html

相关文章:

  • import是如何“占领满屏“
  • ceph /etc/ceph-csi-config/config.json: no such file or directory
  • C语言——验证“哥德巴赫猜想”
  • Flourish笔记:柱状图(Column chart (grouped))
  • 深度学习案例:DenseNet + SE-Net
  • excel文件合并,每个excel名称插入excel列
  • Linux 如何设置特殊权限?
  • 零基础如何使用ChatGPT快速学习Python
  • 【开源】一款基于SpringBoot 的全开源充电桩平台
  • AI - RAG中的状态化管理聊天记录
  • JAVA安全—SpringBoot框架MyBatis注入Thymeleaf模板注入
  • 【STM32系列】提升ADC采样精度的方法
  • 前端面试如何出彩
  • Linux 切换用户的两种方法
  • Spring Boot 3 中Bean的配置和实例化详解
  • Vue实现留言板(实现增删改查)注意:自己引入Vue.js哦
  • IDEA创建Spring Boot项目配置阿里云Spring Initializr Server URL【详细教程-轻松学会】
  • 读取电视剧MP4视频的每一帧,检测出现的每一个人脸并保存
  • HTML前端开发-- Iconfont 矢量图库使用简介
  • 使用Allure作为测试报告生成器(Java+Selenium)
  • RocketMQ面试题合集
  • Qt初识_对象树
  • axios的get和post请求,关于携带参数相关的讲解一下
  • Vue前端开发-路由其他配置
  • 框架建设实战7——定时任务组件
  • mybatis 整合 ehcache
  • 【PlantUML系列】用例图(三)
  • 发送请求时遇到了数据库完整性约束错误 1048 Column ‘platform‘ cannot be null
  • 三菱FX3U模拟量产品的介绍
  • pdf转图片