👻创作者:丶重明
👻创作时间: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 mainimport ("fmt""math"
)func maxSubArray(nums []int) int {maxSum := math.MinIntcurrentSum := 0for _, num := range nums {currentSum += numif 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.😶🌫️代码解析:
-
定义两个变量:
maxSum
和currentSum
。- maxSum:用来存储当前找到的最大子数组和
- currentSum:用来存储当前子数组的和
-
遍历数组,对每个元素累加到
currentSum
中,如果currentSum
小于0,则将其重置为0,表示丢弃当前子数组,开始计算新的子数组。 -
在遍历过程中,每次更新
maxSum
为currentSum
和maxSum
中的最大值。 -
遍历结束后,
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 = 0
,currentSum > maxSum
,所以maxSum = 0
第二个元素为1
,currentSum >= 0
,所以currentSum = 1
,根据文中代码设定,所以maxSum = 1
// 计算方式
currentSum += 1 → 0 + 1 = 1
以此类推,最后可以得出最大子数组和 9
,对应子数组[8, 1]
。
8.😶🌫️扩展:如果数组全为负数
对于全负数数组(如 [-3, -1, -2]),我们需要确保算法能正确返回最大的单个负数(本例中为 -1),请自行尝试。
同系列:
上一篇:【Go每日一练】实现简单的控制台计算器