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

【Go每日一练】计算整数数组的最大子数组和

👻创作者:丶重明
👻创作时间:2025年3月7日
👻擅长领域:运维

目录

  • 1.😶‍🌫️题目:计算整数数组的最大子数组和
  • 2.😶‍🌫️案例资源
  • 3.😶‍🌫️代码开发
  • 4.😶‍🌫️输出结果
  • 5.😶‍🌫️代码解析:
  • 7.😶‍🌫️本文知识点
    • 7.1.😶‍🌫️math包
    • 7.2.😶‍🌫️Kadane算法
  • 8.😶‍🌫️扩展:如果数组全为负数

1.😶‍🌫️题目:计算整数数组的最大子数组和

编写一个Go语言程序 ,计算一个整数数组中的最大子数组和。

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

2.😶‍🌫️案例资源

现有数组整数:

-2, 1, -2, 5, -5, 8, 1, -5, 4

3.😶‍🌫️代码开发

使用Go语言进行代码开发,使用 Kadane 算法,动态地维护当前子数组的和,并在每一步比较是否需要更新最大子数组和。

package main

import (
	"fmt"
	"math"
)

func maxSubArray(nums []int) int {
	maxSum := math.MinInt
	currentSum := 0

	for _, num := range nums {
		currentSum += num

		if currentSum < 0 {
			currentSum = 0
		}

		if currentSum > maxSum {
			maxSum = currentSum
		}
	}
	return maxSum
}

func main() {
	nums := []int{-2, 1, -2, 5, -5, 8, 1, -5, 4}

	result := maxSubArray(nums)
	fmt.Println("最大子数组和为:", result)
}

4.😶‍🌫️输出结果

保存代码,通过go run命令执行代码文件。

> go run .\8.gotest.go
最大子数组和为: 9

5.😶‍🌫️代码解析:

  1. 定义两个变量:maxSumcurrentSum

    • maxSum:用来存储当前找到的最大子数组和
    • currentSum:用来存储当前子数组的和
  2. 遍历数组,对每个元素累加到currentSum中,如果currentSum小于0,则将其重置为0,表示丢弃当前子数组,开始计算新的子数组。

  3. 在遍历过程中,每次更新maxSumcurrentSummaxSum中的最大值。

  4. 遍历结束后,maxSum即为最大子数组和。

7.😶‍🌫️本文知识点

7.1.😶‍🌫️math包

math包是Go语言标准库中的包,提供用于数学运算的常量、函数和工具。
支持基本的数学操作,如三角函数、对数运算、幂运算等,且涵盖了很多高级的数学计算需求。

// 导入math包
import "math"

如:

  • math.Pi:圆周率
  • math.E:自然常数
  • math.Pow(x, y float64) float64:返回 x 的 y 次方

更多使用方法查看官方文档。

本文中出现的math.MinInt就是 int 类型的最小值,它的具体数值取决于平台上 int 类型的位数。

它在很多算法中作为初始化值使用,确保程序可以在后续处理中更新为正确的结果。

7.2.😶‍🌫️Kadane算法

Kadane算法是一种用于高效解决最大子数组和问题的动态规划算法。其核心思想是通过遍历数组并维护两个关键变量:当前子数组的最大和及全局最大和,从而在线性时间复杂度内找到结果。

以本文的一组数字为例:

-2, 1, -2, 5, -5, 8, 1, -5, 4

第一个元素为-2,小于0,根据文中代码设定,小于0时currentSum = 0currentSum > maxSum,所以maxSum = 0

第二个元素为1currentSum >= 0,所以currentSum = 1,根据文中代码设定,所以maxSum = 1

// 计算方式
currentSum += 10 + 1 = 1

以此类推,最后可以得出最大子数组和 9,对应子数组[8, 1]

8.😶‍🌫️扩展:如果数组全为负数

对于全负数数组(如 [-3, -1, -2]),我们需要确保算法能正确返回最大的单个负数(本例中为 -1),请自行尝试。

同系列:

上一篇:【Go每日一练】实现简单的控制台计算器


http://www.kler.cn/a/589008.html

相关文章:

  • 深入解析大语言模型的 Function Call 实现—— 以 Qwen2.5为例
  • 02-Canvas-fabric.ActiveSelection
  • 浅谈Mysql数据库事务操作 用mybatis操作mysql事务 再在Springboot中使用Spring事务控制mysql事务回滚
  • 数学 :矩阵
  • 【Gitee】删除仓库的详细步骤
  • ArcGIS 水利制图符号库:提升水利工作效率的利器
  • 【QT:控件】
  • 第三百八十节 JavaFX教程 - JavaFX区域图
  • 【商城实战(38)】Spring Boot:从本地事务到分布式事务,商城数据一致性的守护之旅
  • 数据结构——单链表list
  • 【软考-架构】11.3、设计模式-新
  • 从技术创新到全球布局:MOVA割草机器人以尖端科技定义智能园艺
  • windows上清理docker
  • NET进行CAD二次开发之二
  • django 运行时仅显示500 但是不提示其他内容 如何令其显示更多错误信息
  • pycharm环境创建
  • 群体智能优化算法-䲟鱼优化算法 (Remora Optimization Algorithm, ROA,含Matlab源代码)
  • Mysql与ElasticSearch间的数据同步场景模拟
  • MySQL数据库(数据库操作)4
  • Vue.js 中的计算属性、监听器与方法:区别与使用场景