Maximum Subarray

Problem statement

Find a contiguous slice of nums (at least one element) whose sum is as large as possible, and return that sum.

Example:

Input:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Expected output:

Why: [4, -1, 2, 1] sums to 6.

Practice on LeetCode: Maximum Subarray

Golang Solution

func maxSubArray(nums []int) int {
    maxSoFar, curSum := nums[0], 0
    j := 0
    for j < len(nums) {
        curSum = curSum + nums[j]
        if curSum > maxSoFar {
            maxSoFar = curSum
        }
        if curSum < 0 {
            curSum = 0
        }
        j += 1
    }
    return maxSoFar
}