Maximum Subarray

1. Problem Description

Given an integer array nums, find the contiguous subarray with the largest sum (the subarray contains at least one element) and return its sum.

2. Approach

1. Approach 1
   • If adding the previous accumulated sum makes the result smaller than the current value itself, restart from the current value

3. Implementation

func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    maxSum := nums[0]
    currentSum := 0
    for _, val := range nums {
        currentSum += val
        if currentSum < val {
            currentSum = val
        }
        maxSum = max(maxSum, currentSum)
    }
    return maxSum
}

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

4. References

• 53. Maximum Subarray - LeetCode