0053.go

// Source: https://leetcode.com/problems/maximum-subarray
// Title: Maximum Subarray
// Difficulty: Easy
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
//
// Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
//
// Example 1:
//
//   Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
//   Output: 6
//   Explanation: [4,-1,2,1] has the largest sum = 6.
//
// Example 2:
//
//   Input: nums = [1]
//   Output: 1
//
// Example 3:
//
//   Input: nums = [0]
//   Output: 0
//
// Example 4:
//
//   Input: nums = [-1]
//   Output: -1
//
// Example 5:
//
//   Input: nums = [-2147483647]
//   Output: -2147483647
//
// Constraints:
//
//   1 <= nums.length <= 2 * 10^4
//   -2^31 <= nums[i] <= 2^31-1
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

package main

func maxSubArray(nums []int) int {
	maxGlobal := nums[0]
	maxEndHere := nums[0]

	for _, num := range nums[1:] {
		maxEndHere = _max(maxEndHere+num, num)
		maxGlobal = _max(maxGlobal, maxEndHere)
	}

	return maxGlobal
}

func _max(a, b int) int {
	if a > b {
		return a
	}
	return b
}