Maximum Subarray - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Maximum Subarray" Problem in Go

Difficulty: Medium | Tags: Array, Divide and Conquer, Dynamic Programming

Introduction

The "Maximum Subarray" problem is a classic algorithmic challenge that tests your understanding of efficient array manipulation and dynamic programming. The goal is to find the contiguous subarray within a given array of integers that has the largest sum.

Problem Analysis

Given an array of integers, we need to identify the contiguous subarray (a sequence of elements within the array) that yields the highest possible sum. For example, in the array [-2,1,-3,4,-1,2,1,-5,4], the subarray [4,-1,2,1] produces the maximum sum of 6. The problem requires an efficient solution due to the constraint of handling large arrays (up to 10^5 elements).

Solution Approach

Kadane's Algorithm is an optimal solution for this problem, offering O(n) time complexity and O(1) space complexity. The algorithm works by iterating through the array while maintaining the maximum sum of the subarray ending at the current position. If the current element alone is greater than the sum of the previous subarray plus the current element, we start a new subarray from the current element.

Go Implementation


func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    maxCurrent := nums[0]
    maxGlobal := nums[0]
    for i := 1; i < len(nums); i++ {
        maxCurrent = max(nums[i], maxCurrent + nums[i])
        if maxCurrent > maxGlobal {
            maxGlobal = maxCurrent
        }
    }
    return maxGlobal
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Complexity Analysis

The time complexity of Kadane's Algorithm is O(n), where n is the number of elements in the array, as we traverse the array only once. The space complexity is O(1) since we use a constant amount of additional space to store intermediate results.

Testing and Examples

Here are some test cases to validate the implementation:

  • Input: [-2,1,-3,4,-1,2,1,-5,4] → Output: 6
  • Input: [1] → Output: 1
  • Input: [5,4,-1,7,8] → Output: 23
  • Input: [-1,-2,-3] → Output: -1

Best Practices and Tips

When implementing Kadane's Algorithm, ensure you handle edge cases such as an array with all negative numbers or a single-element array. Always initialize the maximum values with the first element of the array to avoid incorrect results. For larger datasets, verify that your solution adheres to the O(n) time complexity constraint.

Read more