Kadane's Algorithm (Maximum Subarray)

func maxSubArray(nums []int) int {

}

func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
}

func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]
}

func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]

        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
}

func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur+nums[i])
    }
}

func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur+nums[i])

        // Track the best window we've ever closed off.
    }
}

func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur+nums[i])

        // Track the best window we've ever closed off.
        best = max(best, cur)
    }
}

func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur+nums[i])

        // Track the best window we've ever closed off.
        best = max(best, cur)
    }

    return best // O(n) time, O(1) space
}