Maximum Subarray Sum

Why Maximum Subarray Sum Matters and What We're Solving

Imagine you're staring at a month of stock price changes — some days up, some days down — and you want to know the single best window of time to have held that stock. You don't know it yet, but you've just described one of the most elegant problems in computer science. Grab the free flashcards embedded throughout this lesson to lock in every concept as you go. By the end of this section, you'll understand not just what the Maximum Subarray Sum problem is, but why it keeps appearing in disguise across technical interviews, financial systems, and signal processing pipelines alike.

The Problem, Stated Precisely

Let's be exact. Given an array of integers — which can include negative numbers — find the contiguous subarray whose elements sum to the largest possible value, and return that sum.

The word contiguous is doing enormous work in that sentence. You cannot cherry-pick the five biggest numbers scattered across the array. You must choose a slice: a start index and an end index, and take everything in between.

Consider this array:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Let's map it out visually:

Index:  0   1   2   3   4   5   6   7   8
Value: -2   1  -3   4  -1   2   1  -5   4
                    ^________________^
                    subarray [4,-1,2,1] → sum = 6

The maximum subarray here is [4, -1, 2, 1], starting at index 3 and ending at index 6, with a sum of 6. No other contiguous slice of this array produces a higher total.

🎯 Key Principle: The answer isn't always the longest subarray, and it isn't always the one containing the largest single element. It's the contiguous slice where the cumulative sum peaks — and finding that peak efficiently is the entire challenge.

Why Should You Care? Real-World Relevance

Before we get into algorithms, let's make sure you feel the weight of this problem. The Maximum Subarray Sum pattern is not an academic exercise invented to torture job candidates. It surfaces in real engineering work constantly.

Stock Price Analysis

💡 Real-World Example: A trading algorithm tracks daily profit/loss deltas for a portfolio: [+3, -1, +5, -2, +4, -8, +2]. The question "what was the most profitable continuous holding period?" is exactly the Maximum Subarray Sum problem. The array elements are the day-over-day changes, and the contiguous subarray with the highest sum identifies the optimal buy-and-hold window.

Signal Processing

In digital signal processing, engineers work with waveforms represented as arrays of amplitude values. Identifying the segment of a signal with the greatest energy concentration — useful in noise filtering, audio analysis, and radar — reduces directly to finding the maximum subarray. The "energy" of a segment is proportional to its summed amplitudes.

Game Score Optimization

Multiplayer games often have mechanics where a player's score fluctuates — earning points for kills, losing points for deaths, gaining bonuses, taking penalties. If a developer wants to identify the "hottest streak" a player had in a session (the run of events that contributed most positively to their score), they're solving Maximum Subarray Sum on a sequence of score deltas.

🤔 Did you know? This problem was first formally proposed by Ulf Grenander in 1977 while working on pattern recognition in digitized images. He needed to find the maximum-sum rectangular subarray in a 2D image to identify the brightest region. The 1D version we study today is the elegant foundation of that harder problem.

Why Brute Force Fails at Scale

The most natural instinct when facing this problem is to try every possible subarray. Let's honor that instinct — and then watch it collapse under its own weight.

The O(n³) Approach: Exhaustive and Slow

The most naive solution uses three nested loops: one to fix the start index, one to fix the end index, and one to sum all elements between them.

def max_subarray_brute_force_cubic(nums):
    n = len(nums)
    max_sum = float('-inf')  # Handle all-negative arrays
    
    for i in range(n):           # Start index
        for j in range(i, n):    # End index
            current_sum = 0
            for k in range(i, j + 1):  # Sum the subarray
                current_sum += nums[k]
            max_sum = max(max_sum, current_sum)
    
    return max_sum

For an array of length n, this examines roughly n³/6 operations. Feed it 10,000 elements — a modest dataset in real applications — and you're looking at roughly 166 billion operations. A modern computer running 10⁹ simple operations per second would take about 2.7 minutes just for one query. That is unacceptable.

The O(n²) Approach: Better, Still Broken

A smarter approach eliminates the innermost loop by accumulating the sum as we extend the right boundary:

def max_subarray_quadratic(nums):
    n = len(nums)
    max_sum = float('-inf')
    
    for i in range(n):        # Fix the start index
        current_sum = 0
        for j in range(i, n): # Extend the end index
            current_sum += nums[j]   # Accumulate instead of re-summing
            max_sum = max(max_sum, current_sum)
    
    return max_sum

This is genuinely better — we've cut the work from n³ to n². But scaling still punishes us:

Array size →  1,000     10,000     100,000    1,000,000
O(n²) ops  →  1M       100M        10B         1T
Approx time→  1ms      100ms       ~10s        ~16 min

⚠️ Common Mistake: Many learners see O(n²) and think "that's fine for interview problems." It isn't. LeetCode problems routinely have input sizes of 10⁵ to 10⁶ elements. An O(n²) solution will hit Time Limit Exceeded on those test cases even if your logic is correct.

Brute Force Scaling Visualization:

n=10    ████ (fast)
n=100   ████████████████████ (manageable)
n=1,000 ████████████████████████████████████████ (slow)
n=10,000 ??? (the bar doesn't fit on the page)

O(n) Kadane's:
n=10,000,000 ████ (still fast)

The Mindset Shift: From Enumeration to Decision-Making

Here's where the intellectual leap happens. Both brute force approaches share a common flaw: they think about subarrays as objects to enumerate. "Let me list every possible subarray and measure it."

Kadane's Algorithm — the solution we'll fully unpack in the next section — thinks about the problem differently. It thinks about subarrays as the result of a sequence of local decisions.

As you walk through the array from left to right, at each element you face exactly one question:

"Is it better to extend the subarray I've been building, or to start fresh from this element?"

That's it. One decision per element. The moment you internalize that framing, you've grasped the soul of the algorithm.

💡 Mental Model: Think of yourself as a hiker walking across a mountain range where each step either gains or loses altitude. You're trying to find the journey segment where you gained the most total altitude. At every step, you ask: "Am I better off continuing from where I am, or resetting my baseline to right here?" You never need to look back at every possible starting point — the running total you carry tells you everything.

This is the dynamic programming mindset in its purest form: the answer to the problem at position i depends only on the answer at position i-1, plus a simple local decision. No backtracking, no global enumeration.

🧠 Mnemonic: Think "Keep or Kill." At each element, you either keep the current running sum (extend the subarray) or kill it and start over (begin a new subarray here). The running maximum you maintain throughout is your answer.

A Glimpse at the Core Logic (Before the Full Code)

Without writing the full solution yet, here's the skeleton of the idea expressed in pseudocode:

For each element in the array:
    current_subarray_sum = MAX(element, current_subarray_sum + element)
    max_sum_seen = MAX(max_sum_seen, current_subarray_sum)

Return max_sum_seen

This runs in O(n) time — a single pass through the array. For our 10,000-element example, that's 10,000 operations instead of 100 million. For a million elements, it's a million operations, completing in milliseconds.

What You're Building Toward

📋 Quick Reference Card:

🔒 Approach	⚙️ Time Complexity	📦 Space Complexity	✅ Viable at Scale?
🐌 Triple Loop (Brute Force)	O(n³)	O(1)	❌ No
🚶 Double Loop (Accumulate)	O(n²)	O(1)	❌ No
🚀 Kadane's Algorithm	O(n)	O(1)	✅ Yes

By the time you complete this full lesson, you won't just be able to solve LeetCode #53 (Maximum Subarray). You'll recognize when a problem that looks nothing like this is actually this problem wearing a costume. Problems involving:

🧠 Maximum profit in a single stock transaction 📚 Longest subarray satisfying a condition after transformation 🔧 Maximum sum of a circular subarray 🎯 Finding contiguous regions of maximum value in a grid 🔒 Streaming data analysis with a sliding observation window

...all trace back to the decision logic you're about to master.

💡 Pro Tip: When you see a LeetCode problem involving a contiguous sequence and an optimization over a cumulative quantity, your first instinct should be to ask: "Is this Maximum Subarray in disguise?" That reflex alone will help you crack dozens of problems faster than candidates who try to re-derive everything from scratch.

The stage is set. You understand the problem, you've felt the pain of approaches that don't scale, and you've glimpsed the elegance of the solution. In the next section, we'll tear apart Kadane's Algorithm line by line — the decision logic, the annotated code, and the complexity proof — until it becomes second nature.

Kadane's Algorithm: Core Logic, Code, and Complexity

Now that you understand what the Maximum Subarray Sum problem is asking, it's time to understand how to solve it elegantly. Kadane's Algorithm is one of those rare solutions that feels almost too simple once you grasp it — a single pass through the array, two variables, and a decision made at every step. Let's build this understanding from the ground up.

The Central Insight: A Decision at Every Element

Imagine you're walking through the array one element at a time, carrying a running total. At each new number, you face a fundamental choice: should you add this number to your existing running total, or throw away everything you've accumulated and start fresh from this number?

This is the heart of Kadane's Algorithm, and it can be expressed in a single line:

currentSum = max(num, currentSum + num)

Let's unpack why this decision rule is correct. If your currentSum is negative, then adding it to num would make num smaller than it already is. A negative running total is dead weight — it can only drag down whatever comes next. So you cut your losses and start fresh. On the other hand, if currentSum is positive, it's an asset: adding it to num gives you a larger value than num alone.

🎯 Key Principle: A subarray is only worth extending if what came before it is helping, not hurting. The moment your running total goes negative, it becomes a liability.

💡 Mental Model: Think of it like a road trip tracking net elevation gain. If you've been going downhill (net negative change), you're better off resetting your baseline to wherever you currently stand rather than carrying forward a deficit.

Two Variables Are All You Need

Kadane's Algorithm maintains exactly two variables throughout its single pass:

• currentSum (also called the local maximum): The best subarray sum ending at the current position. It answers the question: "What's the best I can do if the subarray must include this element?"
• globalMax (also called the global maximum): The best subarray sum seen anywhere so far. It answers the question: "What's the best I've found in the entire array up to this point?"

Why only two variables? Because at any given index i, you don't need to remember which previous subarray was best — you only need to remember its value. The decision at index i depends solely on whether currentSum is positive or negative, not on how that sum was achieved. This is what makes the algorithm so space-efficient.

 Array:      [-2,  1, -3,  4, -1,  2,  1, -5,  4]
              ↑
         currentSum tracks the best subarray ending HERE
         globalMax  tracks the best subarray found ANYWHERE

Walking Through a Concrete Example

Let's trace through the classic example array [-2, 1, -3, 4, -1, 2, 1, -5, 4] step by step. The answer should be 6, from the subarray [4, -1, 2, 1].

We initialize currentSum = -2 and globalMax = -2 (both set to the first element).

Index | num | currentSum = max(num, currentSum + num) | globalMax
------+-----+----------------------------------------+----------
  0   |  -2 | max(-2, —) = -2  [initialize]          |    -2
  1   |   1 | max(1, -2 + 1) = max(1, -1) = 1        |     1
  2   |  -3 | max(-3, 1 + -3) = max(-3, -2) = -2     |     1
  3   |   4 | max(4, -2 + 4) = max(4, 2) = 4         |     4
  4   |  -1 | max(-1, 4 + -1) = max(-1, 3) = 3       |     4
  5   |   2 | max(2, 3 + 2) = max(2, 5) = 5          |     5
  6   |   1 | max(1, 5 + 1) = max(1, 6) = 6          |     6
  7   |  -5 | max(-5, 6 + -5) = max(-5, 1) = 1       |     6
  8   |   4 | max(4, 1 + 4) = max(4, 5) = 5          |     6

Notice what happens at index 1: the currentSum was -2, so starting fresh at 1 is better than extending (-2 + 1 = -1). The algorithm correctly identifies that the previous subarray is a liability. At index 3, the same thing happens — currentSum was -2, so we start fresh at 4.

The globalMax is updated at every step to capture the best currentSum seen so far. By the end, globalMax = 6, which is the correct answer.

ASCII visualization of currentSum over time:

Value
  6 |                          ●
  5 |                       ●     ●
  4 |             ●      ●
  3 |                ●
  2 |
  1 |    ●                          ●
  0 |
 -1 |
 -2 | ●         ●
 -3 |
    +----+----+----+----+----+----+----+----+----
    0    1    2    3    4    5    6    7    8

     ← Subarray starting → [4, -1, 2, 1] peaks at index 6

Python Implementation

Here is a clean, annotated Python implementation:

def max_subarray(nums):
    # Edge case: if the array is empty, there's nothing to return
    if not nums:
        return 0

    # Initialize both variables to the first element.
    # We don't start at 0 because the subarray must be non-empty,
    # and all numbers could be negative.
    current_sum = nums[0]
    global_max = nums[0]

    # Start iterating from the second element (index 1)
    for num in nums[1:]:
        # The core decision: extend the current subarray or start fresh?
        # If current_sum is negative, starting fresh (just `num`) is better.
        current_sum = max(num, current_sum + num)

        # Update the global best if the current window is better
        global_max = max(global_max, current_sum)

    return global_max

## Example usage
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # Output: 6
print(max_subarray([-1]))                               # Output: -1
print(max_subarray([5, 4, -1, 7, 8]))                  # Output: 23

⚠️ Common Mistake: Initializing current_sum and global_max to 0 instead of nums[0]. If all numbers in the array are negative (e.g., [-3, -1, -2]), an initialization of 0 would incorrectly return 0 — but 0 represents an empty subarray, which is not valid. The problem requires at least one element. The correct answer for [-3, -1, -2] is -1.

JavaScript Implementation

function maxSubArray(nums) {
  // Guard against empty arrays
  if (nums.length === 0) return 0;

  // Initialize to first element — critical for all-negative arrays
  let currentSum = nums[0];
  let globalMax = nums[0];

  // Loop starting at index 1 — the first element is already "processed"
  for (let i = 1; i < nums.length; i++) {
    const num = nums[i];

    // Extend or restart: the core of Kadane's Algorithm
    currentSum = Math.max(num, currentSum + num);

    // Track the best result encountered across all positions
    globalMax = Math.max(globalMax, currentSum);
  }

  return globalMax;
}

// Example usage
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
console.log(maxSubArray([-1, -2, -3]));                     // -1
console.log(maxSubArray([1]));                              // 1

💡 Pro Tip: Both implementations follow the exact same logic — the only difference is syntax. If you understand one, you understand both. When you're under interview pressure, the two-variable pattern (currentSum, globalMax) is your anchor.

Complexity Analysis

Time Complexity: O(n)

Kadane's Algorithm makes exactly one pass through the array. Every element is visited once, and the work done at each element is constant — two comparisons and two assignments. Therefore, the total time scales linearly with the size of the input, giving us O(n) time complexity.

Space Complexity: O(1)

Regardless of the size of the input array, Kadane's Algorithm only ever uses two extra variables: currentSum and globalMax. No additional arrays, stacks, or data structures are created. This is O(1) (constant) auxiliary space.

Contrast Against Brute Force Approaches

To truly appreciate Kadane's elegance, compare it against naive alternatives:

Approach	Time Complexity	Space Complexity	Description
🐢 Brute Force (all pairs)	O(n²)	O(1)	Try every start/end pair
🐌 Triple Loop	O(n³)	O(1)	Enumerate and sum all subarrays
⚡ Kadane's Algorithm	O(n)	O(1)	Single pass, two variables

The brute force approach works by fixing a start index i and iterating over all possible end indices j ≥ i, computing the sum of each subarray. This results in roughly n²/2 subarray evaluations — fine for small inputs, but it will time out on LeetCode for arrays with 100,000 elements.

## Brute force — O(n²) — DO NOT use in interviews
def max_subarray_brute(nums):
    best = float('-inf')
    for i in range(len(nums)):          # O(n) outer loop
        current = 0
        for j in range(i, len(nums)):   # O(n) inner loop → O(n²) total
            current += nums[j]
            best = max(best, current)
    return best

Kadane's collapses this two-dimensional search space into a single dimension by recognizing that you never need to re-examine past elements. Once you've made the "extend or restart" decision at index i, everything useful from positions 0 through i-1 is already encoded in currentSum.

🧠 Mnemonic: "Keep or Kill" — at each element, you either keep the running total (extend) or kill it and restart. That's the entire algorithm.

🤔 Did you know? Jay Kadane proposed this algorithm in 1984 during a discussion about an O(n log n) approach by Ulf Grenander. Kadane came up with the O(n) solution almost on the spot — it remains one of the most elegant examples of dynamic programming ever devised.

📋 Quick Reference Card:

🎯 Concept	📚 Detail
🔧 Algorithm Type	Dynamic Programming (1D)
🔒 Core Decision	max(num, currentSum + num)
📈 Time Complexity	O(n) — one pass
💾 Space Complexity	O(1) — two variables
⚠️ Init Value	nums[0], not 0
🎯 Output	globalMax

With the core algorithm fully internalized — both conceptually and in code — you're ready to tackle the subtleties that separate good solutions from great ones. The next section covers edge cases, common interview pitfalls, and how this same pattern extends to related problem variants you'll encounter in the wild.

Edge Cases, Common Pitfalls, and Pattern Variations

You now understand Kadane's Algorithm at its core — but understanding an algorithm and being able to deploy it correctly under pressure are two very different things. Interview problems are designed to expose exactly the gaps between those two states. This section is your armor. We'll dissect the edge cases that silently break otherwise correct implementations, expose the common mistakes that cost candidates their offers, and then zoom out to show you how the same thinking pattern powers a whole family of LeetCode problems.

---

The All-Negative Array Trap

This is the single most common source of wrong answers on this problem. Consider the array [-3, -1, -4, -2]. The correct answer is -1 — the least negative single element. But if your implementation initializes globalMax to 0, it will return 0, which corresponds to the empty subarray. That's wrong for most problem formulations, which require at least one element to be selected.

❌ Wrong thinking: "The maximum subarray sum can't be negative, so starting from 0 is a safe baseline."

✅ Correct thinking: "The maximum subarray must contain at least one element. The baseline should be the worst possible value, not zero."

🎯 Key Principle: When the problem states the subarray must be non-empty, always initialize globalMax to the first element of the array, not to 0. This single change is the difference between a correct and incorrect solution on all-negative inputs.

Here's a side-by-side comparison of the broken and correct initialization:

## ❌ WRONG: Initializes globalMax to 0
def max_subarray_wrong(nums):
    current_sum = 0
    global_max = 0  # BUG: returns 0 for all-negative arrays

    for num in nums:
        current_sum = max(num, current_sum + num)
        global_max = max(global_max, current_sum)

    return global_max

## ✅ CORRECT: Initializes globalMax to first element
def max_subarray(nums):
    current_sum = nums[0]  # Start from first element
    global_max = nums[0]   # Baseline is the first element, not 0

    for num in nums[1:]:   # Iterate from second element onward
        current_sum = max(num, current_sum + num)
        global_max = max(global_max, current_sum)

    return global_max

## Test on all-negative array
print(max_subarray_wrong([-3, -1, -4, -2]))  # Returns 0 ❌
print(max_subarray([-3, -1, -4, -2]))        # Returns -1 ✅

💡 Mental Model: Think of globalMax as a scoreboard for a competition where someone must win. Even if all scores are negative, the least-negative score still takes first place. Initializing to 0 is like saying "no one wins unless they score positively" — which violates the rules of the game.

🧠 Mnemonic: "First is Fair" — when in doubt, your initial max should be the first element, not zero.

---

Empty and Single-Element Arrays: Defensive Coding

In a real LeetCode submission, the constraints usually guarantee nums.length >= 1, so an empty array may not be a concern. But in a system design or production coding context — and sometimes in interviews where the interviewer deliberately leaves constraints vague — you need to handle these defensively.

Single-element arrays are actually handled correctly by the initialized-to-first-element approach above. If nums = [7], the loop over nums[1:] simply never executes, and global_max returns 7. Clean and correct.

Empty arrays require an explicit guard. The standard professional habit is to check at the top of the function:

def max_subarray_safe(nums):
    # Defensive guard for empty input
    if not nums:
        raise ValueError("Input array must contain at least one element")
        # Alternatively: return 0, return None, or return float('-inf')
        # depending on your contract with the caller

    current_sum = nums[0]
    global_max = nums[0]

    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        global_max = max(global_max, current_sum)

    return global_max

💡 Pro Tip: In interviews, verbally acknowledge constraints before you code. Say: "I'll assume the array has at least one element based on the problem constraints, but I'll add a guard just in case." This signals maturity and professional instinct to your interviewer — even if they never actually test the empty case.

---

Returning the Actual Subarray Indices

LeetCode #53 only asks for the sum. But a very common interview follow-up is: "Now return the starting and ending indices of that subarray." This catches people off guard because they've been thinking only about values, not positions.

The good news: you can track indices with a few extra variables without changing the time or space complexity at all — still O(n) time, O(1) space.

The key insight is that there are three index variables to maintain:

tempStart  → where the current window would start if we extend it
start      → the confirmed start of the best subarray found so far
end        → the confirmed end of the best subarray found so far

Whenever current_sum resets to the current element (meaning we've abandoned the previous window), tempStart advances to the current position. Whenever current_sum beats globalMax, we commit tempStart to start and the current index to end.

def max_subarray_with_indices(nums):
    if not nums:
        raise ValueError("Array must be non-empty")

    current_sum = nums[0]
    global_max = nums[0]

    temp_start = 0  # Candidate start for the current window
    start = 0       # Confirmed start of the best subarray
    end = 0         # Confirmed end of the best subarray

    for i in range(1, len(nums)):
        # Decision: extend current window or start fresh?
        if nums[i] > current_sum + nums[i]:
            # Starting fresh — the old window is dead weight
            current_sum = nums[i]
            temp_start = i  # New candidate start
        else:
            current_sum += nums[i]

        # Update best if we've found a new maximum
        if current_sum > global_max:
            global_max = current_sum
            start = temp_start  # Commit the candidate start
            end = i             # This index is the new best end

    return global_max, start, end

## Example walkthrough
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result_sum, s, e = max_subarray_with_indices(nums)
print(f"Max sum: {result_sum}")          # 6
print(f"Subarray: {nums[s:e+1]}")        # [4, -1, 2, 1]
print(f"Indices: [{s}, {e}]")            # [3, 6]

Let's trace through the critical transitions visually:

Index:       0   1   2   3   4   5   6   7   8
Array:      -2   1  -3   4  -1   2   1  -5   4

current:    -2   1  -2   4   3   5   6   1   5
tempStart:   0   1   1   3   3   3   3   3   3
globalMax:  -2   1   1   4   4   5   6   6   6
start/end:   -   -   -  3,3  -  3,5 3,6  -   -  ← commits happen here

Final answer: indices [3, 6] → subarray [4, -1, 2, 1] → sum = 6 ✅

💡 Pro Tip: Practice explaining the three-pointer approach out loud. Interviewers love seeing you articulate why tempStart differs from start — it shows you understand the lazy-commit pattern rather than just memorizing code.

---

The Critical Reset Mistake

This is the subtlest bug and the one most likely to slip past a quick code review.

⚠️ Common Mistake — Mistake 1: Resetting currentSum to 0 instead of to the current element when starting a new window. ⚠️

## ❌ WRONG reset
if current_sum < 0:
    current_sum = 0      # You've now lost the current element!

## ✅ CORRECT decision
current_sum = max(nums[i], current_sum + nums[i])  # Always includes nums[i]

Why does this matter? If you reset to 0 and then add the next element, you're effectively saying "I'll start a new window after this element." But Kadane's guarantees every element gets considered as a potential window member or window starter. Resetting to 0 creates a silent off-by-one that only manifests in specific edge cases — making it extremely hard to catch without a targeted test.

🎯 Key Principle: The choice at each step is binary: "take this element alone" vs. "extend the previous window with this element." There is no third option of "skip this element and start fresh later."

---

Pattern Extensions: The Kadane Family of Problems

Once you truly understand Kadane's Algorithm, you'll recognize it as the seed of an entire problem family. Here are three natural extensions you'll encounter on LeetCode.

Maximum Product Subarray (LeetCode #152)

Products behave differently than sums because two negatives multiply to a positive. The key extension: track both the current maximum and current minimum at each step, because the minimum (most negative) can become the maximum when multiplied by a negative number.

🔧 Core change: Maintain current_max and current_min, and swap them when you encounter a negative number. The overall structure is still O(n) time, O(1) space.

Circular Subarray Sum (LeetCode #918)

In a circular array, the subarray can wrap around the end and reconnect at the beginning. The elegant insight: the answer is either

• the standard Kadane result (no wrap-around), OR
• total_sum - minimum_subarray_sum (the wrap-around case removes the minimum middle portion)

This transforms the problem into running Kadane's twice — once for maximum, once for minimum — then taking the better result.

🧠 Mnemonic: "Circular = Direct OR Complement" — either the best subarray lives in the middle, or it wraps around (which is equivalent to removing the worst middle section).

Minimum Subarray Sum (LeetCode #1749 variant)

This is a direct inversion of Kadane's. Flip every max to min, initialize to the first element, and you'll find the most negative contiguous subarray. This becomes a building block for the circular sum problem above.

🤔 Did you know? Kadane's Algorithm was first described by computer scientist Jay Kadane in 1984, in response to a challenge posed by Ulf Grenander who needed an O(n) solution for a 2D pattern recognition problem. The 1D version we use today was the elegant simplification that made it into textbooks.

---

---

Summary

You've now completed the full picture of Maximum Subarray Sum — from intuition to implementation to hardened, interview-ready mastery.

📋 Quick Reference Card:

🔍 Scenario	❌ Pitfall	✅ Fix
🔴 All-negative array	Initialize globalMax = 0	Initialize globalMax = nums[0]
🟡 Empty array	No guard clause	Add if not nums check
🟢 Single element	Off-by-one in loop	Loop from index 1, initialized to index 0
🔵 Track indices	Forget tempStart	Use three pointers: tempStart, start, end
🟣 Reset logic	Reset to 0	Reset to max(num, current + num)
⚪ Circular array	Ignore wrap-around	Total sum minus minimum subarray

What you now understand that you didn't before:

🧠 You understand why initialization matters, not just what to initialize — the difference between correctness and coincidental correctness.

📚 You can extend a single algorithmic idea (the local-vs-global max decision) into tracking indices, handling circularity, and flipping to minimums — all without relearning anything from scratch.

🔧 You have the defensive coding habits (guard clauses, constraint verbalization) that signal professional seniority in interviews.

⚠️ Final critical points to remember:

• Never initialize globalMax to 0 unless the problem explicitly allows an empty subarray.
• The reset choice is always max(num, current + num) — never a bare 0 reset.
• Every Kadane variant preserves O(n) time and O(1) space — if your solution doesn't, you've taken a wrong turn.

Practical next steps:

1. 🎯 Solve LeetCode #53 from memory, then immediately attempt #152 (Maximum Product Subarray) to cement the transition.
2. 🔧 Practice the index-tracking version in a mock interview setting — have a friend ask for it as a follow-up.
3. 📚 Study LeetCode #918 (Maximum Sum Circular Subarray) as your capstone — it combines everything: Kadane's core, the minimum variant, and the total-sum complement trick all in one problem.