「Kadane算法」动态规划：求连续子数组最大值

2025-3-4 diaba 算法

package main

import (
	"fmt"
)

// maxSubarraySum 计算数组的最大连续子数组和
// 如果最大和是正数，返回该值；如果是负数或0，返回0
func maxSubarraySum(arr []int) int {
	if len(arr) == 0 {
		return 0
	}

	currentMax := 0
	globalMax := 0

	for _, num := range arr {
		currentMax = max(0, currentMax+num) // 更新当前子数组的最大和
		if currentMax > globalMax {
			globalMax = currentMax // 更新全局最大和
		}
	}

	return globalMax
}

// max 返回两个整数中的较大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	// 示例测试
	arr1 := []int{1, 2, -1, 3, 4, -2}
	arr2 := []int{2, -1, 2, 3, 4, -5}
	arr3 := []int{-1, -2, -3}
	arr4 := []int{1, 2, 3, 4, 5}
	arr5 := []int{1, 2, -1, -3, -4, 3, -2, 5, 2}

	fmt.Println(maxSubarraySum(arr1)) // 输出：9
	fmt.Println(maxSubarraySum(arr2)) // 输出：10
	fmt.Println(maxSubarraySum(arr3)) // 输出：0
	fmt.Println(maxSubarraySum(arr4)) // 输出：15
	fmt.Println(maxSubarraySum(arr5)) // 输出： 8
}

« Redis 的 ZSET（Sorted Set，有序集合） | Redis数据结构介绍»

发表评论：