package main

// important. maxLeft: maximum of sum(nums[x], nums[i])
func maxSubArray(nums []int) int {
	max, maxLeft := nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		maxLeft = maxInt(maxLeft+nums[i], nums[i])
		max = maxInt(max, maxLeft)
	}
	return max
}