LeetCode53-Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
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.

algorithm that operates on arrays: it starts at the left end (element A[1]) and scans through to the right end (element A[n]), keeping track of the maximum sum subvector seen so far. The maximum is initially A[0]. Suppose we've solved the problem for A[1 .. i - 1]; how can we extend that to A[1 .. i]? The maximum
sum in the first I elements is either the maximum sum in the first i - 1 elements (which we'll call MaxSoFar), or it is that of a subvector that ends in position i (which we'll call MaxEndingHere).

MaxEndingHere is either A[i] plus the previous MaxEndingHere, or just A[i], whichever is larger.

func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    maxSoFar := nums[0]
    maxEndHere := nums[0]
    
    for i:= 1; i< len(nums); i++ {
        maxEndHere = int( math.Max(float64(maxEndHere + nums[i]), float64(nums[i])))
        maxSoFar = int(math.Max(float64(maxSoFar), float64(maxEndHere)))
    }
    
    return maxSoFar
}

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

	return divideAndConquer(nums, 0, len(nums))
}

func divideAndConquer(nums []int, from, end int) int {
	if end-from == 1 {
		return nums[from]
	}
	middle := from + (end-from)/2

	maxLeft := divideAndConquer(nums, from, middle)
	maxRight := divideAndConquer(nums, middle, end)

	continuousMax := continuousMaxLeft(nums, from, middle) + continuousMaxRight(nums, middle, end)

	return max(max(maxLeft, maxRight), continuousMax)
}

func continuousMaxLeft(nums []int, from, end int) int {
	m := nums[end-1]
	cm := m
	for i := end - 2; i >= from; i-- {
		cm = cm+nums[i]
		m = max(m, cm)
	}
	return m;
}

func continuousMaxRight(nums []int, from, end int) int {
	m := nums[from]
	cm := m
	for i := from + 1; i < end; i++ {
		cm = cm+nums[i]
		m = max(m, cm)
	}
	return m
}
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}