// ++++++++++++++++++++++++++++++++++++++++
// 《零基础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 maxSubArray(array []int) int {
	// 子数组必须至少有一个元素，因此最大和被初始化为 array 中的第1个元素
	maxSum := array[0]

	//迭代 array 中的其余元素
	for i := 1; i < len(array); i++ {
		// 如果前一个元素的值大于0，则将其添加到当前元素
		if array[i-1] > 0 {
			array[i] += array[i-1]
		}

		//如果当前总大于maxSum，则更新最大总和
		if array[i] > maxSum {
			maxSum = array[i]
		}
	}

	//返回最大总和
	return maxSum
}

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

	//使用 Kadane 算法计算 array 中连续子数组的最大总和
	max := maxSubArray(array)

	//打印结果
	fmt.Println("连续子数组的最大和：", max)
}

//$ go run interview10-2.go
//连续子数组的最大和： 6