【数据结构与算法】Kadane‘s算法(动态规划、最大子数组和)

2023-11-21 00:04

本文主要是介绍【数据结构与算法】Kadane‘s算法(动态规划、最大子数组和),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 一、算法原理
  • 二、例题
    • 2.1 最大子数组和
    • 2.2 环形子数组的最大和

一、算法原理

Kadane's算法是一种用于解决最大子数组和问题的动态规划算法。这类问题的目标是在给定整数数组中找到一个连续的子数组,使其元素之和最大(数组含有负数)。

算法的核心思想是通过迭代数组的每个元素,维护两个变量来跟踪局部最优解和全局最优解。

以下是Kadane’s算法的详细步骤:

  1. 初始化:

    • 令 maxEndingHere 表示在当前位置结束的最大子数组和,初始值为数组的第一个元素。
    • 令 maxSoFar 表示全局最大子数组和,初始值也为数组的第一个元素。
  2. 迭代:

    • 从数组的第二个元素开始迭代。

    • 对于每个元素,计算在当前位置结束的最大子数组和:
      maxEndingHere = max(nums[i], maxEndingHere + nums[i]);
      这表示要么继续当前子数组,要么从当前位置开始一个新的子数组。

    • 更新全局最大子数组和:
      maxSoFar = max(maxSoFar, maxEndingHere);
      如果在当前位置结束的子数组和大于全局最大和,更新全局最大和。

  3. 返回结果:

    • 当迭代完成后,maxSoFar 中存储的即为最大子数组和。

复杂度:

  • 时间复杂度:O(n),其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
  • 空间复杂度:O(1)。我们只需要常数空间存放若干变量。

图例:
在这里插入图片描述

简要说明:(如过当前值比前面的局部最大值+当前值还大,那么就从当前值开始继续计算局部最大值)

  1. i=0,maxEndingHere 、maxSoFar 初始值都为数组第一个元素,-2;
  2. 开始循环,i=1,maxEndingHere = max(nums[1], maxEndingHere + nums[1]),即maxEndingHere = max(1, -2 + 1)=1,maxSoFar=1;
  3. i=2, maxEndingHere = max(nums[2], maxEndingHere + nums[2]),即maxEndingHere = max(-3, 1 - 3)=-2,maxSoFar=1;
  4. i=3,maxEndingHere = max(nums[3], maxEndingHere + nums[3]),即maxEndingHere = max(4, -2 + 4)=4,maxSoFar=4;

二、例题

2.1 最大子数组和

在这里插入图片描述

解答:

int maxSubArray(int* nums, int numsSize) {int maxEndingHere  = nums[0], maxSoFar = nums[0];for (int i = 1; i < numsSize; i++) {maxEndingHere  = fmax(maxEndingHere  + nums[i], nums[i]);maxSoFar = fmax(maxSoFar, maxEndingHere );}return maxSoFar;
}

fmax是<math.h>中的函数,用于比较2个数字的大小,双精度。

简单换个写法:

int maxSubArray(int* nums, int numsSize) {int maxEndingHere  = nums[0], maxSoFar = nums[0];for (int i = 1; i < numsSize; i++) {maxEndingHere  = maxEndingHere  + nums[i]>nums[i]?maxEndingHere  + nums[i]:nums[i];maxSoFar = maxSoFar>maxEndingHere?maxSoFar:maxEndingHere;}return maxSoFar;
}

简单用三目表达式代替fmax函数。

2.2 环形子数组的最大和

在这里插入图片描述

解答:

int maxSubarraySumCircular(int* nums, int numsSize) {if (nums == NULL || numsSize == 0) return 0;int maxSum = nums[0], minSum = nums[0];int maxCur = nums[0], minCur = nums[0];int sum = nums[0];for (int i = 1; i < numsSize; i++) {sum += nums[i];maxCur = fmax(nums[i], maxCur + nums[i]);minCur = fmin(nums[i], minCur + nums[i]);maxSum = fmax(maxSum, maxCur);minSum = fmin(minSum, minCur);}if (maxSum < 0) return maxSum; // 如果所有数都是负数,返回最大值return fmax(maxSum, sum - minSum); // 返回“不跨越头尾的最大子数组和”和“跨越头尾的最大子数组和”中的较大者
}

这篇关于【数据结构与算法】Kadane‘s算法(动态规划、最大子数组和)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL