4 ms 4.3 MB

53_1.go

func maxSubArray(nums []int) int {
	if len(nums) <= 0 {
		return 0
	}

	arr := []int{}
	sum := 0
	max := nums[0]

	for i := 0; i < len(nums); i++ {
		if nums[i] > max {
			max = nums[i]
		}

		if nums[i] < 0 && !checkBackwardForPositive(nums[i], arr) {
			arr = []int{}
			sum = 0
			continue

		}
		
		
		arr = append(arr, nums[i])
		sum += nums[i]
		if sum > max {
			max = sum
		}

	}

	return max
}

func checkBackwardForPositive(v int, arr []int) bool {
	sum := v

	for i := (len(arr) - 1); i >= 0; i-- {

		sum += arr[i]
		if sum > 0 {
			return true
		}
	}

	return false

}