package main

import (
	"fmt"
	"math"
)

// maxSubArray 給訂一組數字找到一組子陣列，這組子陣列的總和是最大的，最後 return 總和。

func maxSubArray(nums []int) int {
	// 先定義目前最大的數字，最後就回傳這個數字
	maxSum := math.MinInt
	tmpSum := 0

	for _, item := range nums {
		tmpSum += item
		// 更新 maxSum 為當前最大的子陣列和
		maxSum = max(maxSum, tmpSum)
		// 如果 tmpSum 小於 0，則重置為 0，從下一個元素重新開始累加
		if tmpSum < 0 {
			tmpSum = 0
		}
	}

	return maxSum
}

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

	fmt.Println(maxSubArray(nums), maxSubArray(nums) == 6)
}