// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 返回两个整数中的最大值
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// 返回 array 中任何连续子数组的最大总和
func maxSubarraySum(array []int) int {
	//初始化两个变量
	maxSoFar, maxEndingHere := 0, 0
	//遍历数组中的每个元素
	for _, num := range array {
		//将 maxEndingHere 更新为当前元素的最大值
		maxEndingHere = max(num, maxEndingHere+num)
		//更新 maxSoFar 为之前的 maxSoFar 和当前的 maxEndingHere 中的最大值
		maxSoFar = max(maxSoFar, maxEndingHere)
	}
	//返回到目前为止看到的最大总和
	return maxSoFar
}

func main() {
	//使用示例数组测试 maxSubarraySum() 函数
	array := []int{1, -2, 3, 4, -5, 8}
	fmt.Println("数组：", array)
	fmt.Println("最大子数组和：", maxSubarraySum(array))
}

//$ go run kadane.go
//数组： [1 -2 3 4 -5 8]
//最大子数组和： 10