NUHMAN.com

Introduction

LeetCode 53: Maximum Subarray is a classic problem that appears frequently in coding interviews and algorithm discussions. The goal is to find a contiguous subarray with the largest sum from an integer array.

While brute-force methods exist, the optimal solution uses Kadane’s Algorithm, which allows us to solve the problem in linear time.

Problem Statement

Given an integer array nums, find the subarray (contiguous elements) which has the largest sum and return its sum.

Example:

go

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum = 6.

Constraints

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴

Approach: Kadane’s Algorithm

Kadane’s Algorithm is based on a simple observation:

• At each index i, we decide whether to:

1. Start a new subarray at i, or
2. Extend the previous subarray including i.

We track:

• currentSum: The max sum ending at the current index.
• maxSum: The overall maximum seen so far.

Decision Rule:

go

currentSum = max(nums[i], currentSum + nums[i])
maxSum = max(maxSum, currentSum)

Go Implementation

go

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

    currentSum := nums[0]
    maxSum := nums[0]

    for i := 1; i < len(nums); i++ {
        currentSum = max(nums[i], currentSum+nums[i])
        maxSum = max(maxSum, currentSum)
    }

    return maxSum
}

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

Example Walkthrough

Given nums = [-2,1,-3,4,-1,2,1,-5,4]:

IndexNumcurrentSummaxSum0-2-2-211max(1, -2+1) = 112-3max(-3, 1-3) = -2134max(4, -2+4) = 444-1max(-1, 4-1) = 3452max(2, 3+2) = 5561max(1, 5+1) = 667-5max(-5, 6-5) = 1684max(4, 1+4) = 56

Answer: 6

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• One pass through the array.
• Only a few variables used for tracking.

Edge Cases

• All numbers negative: The highest (least negative) number will be the max sum.
• Single element array: Return the element itself.
• Large positive/negative mixes: Kadane’s will handle transitions naturally.

Key Takeaways

• Kadane’s Algorithm is a powerful and elegant solution to find maximum subarray sum.
• Runs in linear time with constant space.
• The concept can be extended to track subarray indices, 2D matrices, or variations.