Pattern #33

Kadane’s Algorithm

Important interview questions, thinking patterns, maximum subarray sum, all-negative arrays, tracking range indices, Circular & Product variants, and Go rules.

Must Solve

10 core questions — solve these first.

1.Maximum Subarray
Classic Kadane: current = max(nums[i], current + nums[i]), best = max(best, current)medium
2.Maximum Sum Circular Subarray
Circular Kadane: max(normalMax, totalSum - minSubarraySum)medium
3.Maximum Product Subarray
Track BOTH currentMax & currentMin (neg * neg flips min <-> max)medium
4.Best Time to Buy and Sell Stock
Kadane on price differences or min price trackingeasy
5.Maximum Sum Subarray with One Deletion
DP/Kadane tracking 0 deletions and 1 deletion statemedium
6.Maximum Absolute Sum of Any Subarray
Max Kadane (positive sum) vs Min Kadane (negative sum)medium
7.Maximum Subarray Sum After One Operation
State machine Kadane before and after squaring an elementmedium
8.Maximum Sum of Two Non-Overlapping Subarrays
Left & Right prefix/suffix Kadane windowsmedium
9.Maximum Subarray Min-Product
Monotonic Stack for min element range + Prefix Summedium
10.K-Concatenation Maximum Sum
Kadane on k=1, k=2 + math on total sum for k >= 3medium

Also Important

7 more questions worth practicing.

11.Maximum Alternating Subarray Sum
State machine Kadane tracking odd & even index signsmedium
12.Maximum Subarray Sum with Length Constraint
Deque / Prefix Sum window boundshard
13.Maximum Sum Rectangle in a 2D Matrix
2D Kadane: Compress rows + 1D Kadane on column sumshard
14.Largest Sum Contiguous Subarray
Standard Kadane algorithm formulationmedium
15.Maximum Subarray with Start/End Index
Kadane tracking tempStart, start, end indicesmedium
16.Minimum Subarray Sum
Inverted Kadane: current = min(nums[i], current + nums[i])medium
17.Maximum Difference / Profit Variants
Single pass min value trackingeasy

How to Think

Need maximum sum of a continuous subarray?Kadane’s Algorithm
Continuous part + max/min sum?Running best tracking
Current running sum becomes harmful?Drop it! Start fresh at nums[i]
Need maximum product instead of sum?Track BOTH max AND min (neg * neg = pos)

Go Kadane Code Template

Standard O(N) Time, O(1) Space Kadane in Go

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

    // 1. Initialize with first element (safe for all-negative arrays!)
    curSum := nums[0]
    bestSum := nums[0]

    for i := 1; i < len(nums); i++ {
        // 2. Decide: Continue previous or start fresh at nums[i]
        if curSum+nums[i] > nums[i] {
            curSum = curSum + nums[i]
        } else {
            curSum = nums[i] // Drop bad negative past!
        }

        // 3. Track global maximum seen anywhere
        if curSum > bestSum {
            bestSum = curSum
        }
    }
    return bestSum
}

👉 Time: O(N) | Space: O(1)

All-Negative Array Handling ([-5, -2, -8])

If an array contains only negative numbers like [-5, -2, -8], the correct non-empty maximum subarray sum is -2 (NOT 0!).

❌ Zero Initialization Mistake

Setting cur = 0, best = 0 causes all-negative arrays to return 0 instead of the maximum single element (-2).

✅ First Element Initialization

Setting cur = nums[0], best = nums[0] guarantees non-empty subarray evaluation for negative inputs!

Tracking Actual Subarray [Start, End] Indices

When an interviewer asks for the actual continuous subarray bounds [start, end]:

func maxSubArrayWithIndices(nums []int) (int, int, int) {
    curSum, bestSum := nums[0], nums[0]
    start, end, tempStart := 0, 0, 0

    for i := 1; i < len(nums); i++ {
        if curSum + nums[i] > nums[i] {
            curSum += nums[i]
        } else {
            curSum = nums[i]
            tempStart = i // Restarting new candidate subarray!
        }

        if curSum > bestSum {
            bestSum = curSum
            start = tempStart
            end = i // Capture new peak boundaries!
        }
    }
    return bestSum, start, end
}

Circular & Product Subarray Variants

Maximum Sum Circular Subarray

Wrapped sum = TotalSum - minSubarraySum. Final answer = max(normalMax, totalSum - minSubarraySum) (unless all negative!).

Maximum Product Subarray

Track BOTH currentMax AND currentMin! A negative multiplier flips min $\leftrightarrow$ max. Swap min/max when encountering negative values.

Visual Memory Rule

cur = max(x, cur + x)
best = max(best, cur)

All negative array  → Initialize cur = nums[0], best = nums[0]
Track Range         → Set tempStart = i on restart, start = tempStart when best updates
Product Subarray    → Track BOTH max AND min

💡 Golden Rule: "If the previous sum makes the current position worse, throw it away and start again."

Common Interview Mistakes

1. Resetting to Zero

Initializing cur = 0, best = 0 fails on all-negative arrays. Always initialize with nums[0].

2. Returning Only Current

Returning curSum at the end instead of bestSum (the peak subarray sum may have ended earlier!).

3. Confusing Subarray with Subsequence

Kadane requires CONTINUOUS elements. In [5, -100, 6], picking [5, 6] is invalid!

4. Using Product Kadane Without Min

Tracking only currentMax for product subarrays loses track of negative pairs multiplying into large positive products!

Interview Rules

1. Maximum continuous sum? → Kadane’s Algorithm
2. Core formula → cur = max(nums[i], cur + nums[i])
3. Global best → best = max(best, cur)
4. All-negative array? → Initialize cur = nums[0], best = nums[0]
5. Need actual range? → Track tempStart, start, end
6. Circular maximum? → max(normalMax, totalSum - minSubarraySum)
7. Maximum product? → Track BOTH currentMax AND currentMin
8. Overall Complexity → O(N) time, O(1) space

Small Rules

Rule 1: Always initialize current and best with nums[0].
Rule 2: At every item, decide between continuing previous sum vs starting fresh at nums[i].
Rule 3: Always track global best separately from current ending sum.
Rule 4: Kadane applies strictly to contiguous subarrays, not non-contiguous subsequences.
Rule 5: Product Kadane requires maintaining min and max due to negative multiplication sign flips.

Production Thinking

Financial Profit/Loss Streak → Find the strongest continuous profitable trading window

System Performance Changes → Locate the peak continuous performance improvement run in minute metrics

Financial Returns Gain Period → Identify maximum continuous gain duration across portfolio returns

A/B Testing Impact Evaluation → Identify highest continuous positive impact bucket sequence

Remember This

Kadane
→ Maximum continuous sum

At every position:

Continue
→ current + nums[i]

Restart
→ nums[i]

Take bigger

current → best ending HERE
best    → best ANYWHERE

Time  → O(n)
Space → O(1)

All negative → start from nums[0]

💡 Golden Rule: "If the previous sum makes the current position worse, throw it away and start again."