DSA sheet · Arrays · Kadane's Algorithm pattern

Maximum Subarray (Kadane's Algorithm)

This is the first question of the Kadane's algorithm section of the sheet. The teacher first solves it with a brute force (two loops that add up every subarray), shows that it gets TLE, then goes through her four array patterns one by one and explains why only Kadane's fits. Kadane's itself is one short loop with one rule: keep a running sum, and the moment it goes negative, throw it away and start again.

Why it matters: sliding window, which we used in the earlier problems, breaks as soon as the array has negative numbers. Kadane's is the tool for "best subarray sum" when negatives are allowed, and the next problem (Maximum Product Subarray) builds on the same "keep it or restart" thinking.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (subarrays and Kadane's idea from scratch)
• Part A · Brute force: add up every subarray
• Part B · Optimal: Kadane's algorithm
• Part C · Revision page

Part 0 · Before starting

What is a subarray?

A subarray is a piece of the array whose elements sit next to each other (they are contiguous). Pick a start index and an end index and take everything in between, without skipping anything. If you are allowed to skip elements, that is a subsequence, a different thing. The teacher stresses this: here we want the continuous one.

The brute force over all subarrays

Every subarray is fixed by its start i and its end j (with i ≤ j). Two loops can visit them all: the outer loop fixes i, the inner loop moves j from i to the end and keeps adding one more element to a running sum. There are n·(n+1)/2 subarrays, so this is O(n²). It repeats a lot of work: every new start i adds up almost the same numbers again from scratch.

Kadane's idea: at every index, extend or start fresh

Walk through the array once. At each index i, think about the best subarray that ends exactly at i. There are only two choices for it:

• Extend: take the best subarray that ended at i − 1 and add nums[i] to it.
• Start fresh: begin a new subarray at i, containing only nums[i].

Extending is better only if what we carry from the past is positive. If the running sum from the past is negative, carrying it can only pull the new total down, so we drop it and start again. In the teacher's code this looks like: add the number to a running sum, update the best answer, and if the running sum went below zero, set it back to 0 (an empty start, so the next number begins fresh).

Why dropping a negative running sum is safe

Suppose the running sum of some stretch [a..k] is negative. Take any subarray that starts at a (or earlier inside that stretch) and keeps going past k, say up to m. Its sum is (sum of [a..k]) + (sum of [k+1..m]). The first part is negative, so cutting it off gives [k+1..m], which has a bigger sum. So a best subarray never begins with a piece whose sum is negative. Throwing that piece away can never lose the best answer.

And it's only "negative" that matters, not "got smaller". A sum that drops from 4 to 3 is still positive, so it still helps whatever comes next. The teacher shows this with 4, −1, 2 later.

The all-negative case

If every number is negative, every running sum is negative and gets reset at once. The answer must then be the largest single number (a subarray must contain at least one element, so "take nothing, sum 0" is not allowed). Two details make the code give that:

• the best answer starts at nums[0] (or −∞), never 0;
• we update the best answer before resetting the running sum, so each single number gets its chance to be recorded.

How this relates to sliding window, and why a plain window fails here

Sliding window keeps a window [left..right], grows it with right and shrinks it with left. That only works when the rule is monotonic: adding an element always pushes the sum one way and removing one always pushes it the other way. Then "grow until invalid, then shrink" never skips a good window.

With negatives this breaks. Adding −3 makes the sum smaller, and later adding 4 makes it bigger again. A window can't tell whether to shrink now: dropping a negative on the left raises the sum, dropping a positive lowers it. There is no simple "valid / invalid" rule to grow and shrink by. Kadane's still has a moving start (where the current run began) and a moving end (i), like a window. The difference is that the start doesn't creep forward one step at a time. It jumps straight to i + 1 when the running sum turns negative, and the proof above tells us that jump is safe.

The teacher's 4 array patterns

Part A · Brute force: add up every subarray

LeetCode 53

1The question in simple words

You get an integer array nums. Among all its (non-empty) subarrays, find the one with the largest sum, and return that sum (not the subarray itself).

The teacher starts by trying a few subarrays from the left: [−2] has sum −2, [−2, 1] has −1, [−2, 1, −3] has −4, and so on. None of them comes close to 6, which is [4, −1, 2, 1].

2What the constraints tell us

• 1 ≤ n ≤ 10⁵. O(n²) would be about 10¹⁰ steps. Beyond roughly 10⁸ the code may get TLE, so we will have to optimise. The brute force is only a starting point.
• −10⁴ ≤ nums[i] ≤ 10⁴. The teacher points out that numbers can be negative. This line is what decides the pattern later: negatives rule out sliding window and point to Kadane's.
• n ≥ 1, so there is always at least one element and the answer always exists.
• The largest possible sum is 10⁵ × 10⁴ = 10⁹, which fits in a normal int. (Python ints never overflow anyway.)

3Intuition: list every subarray, keep the best

If we can produce every subarray's sum, we just keep the largest one. To produce them: stand at a start index i, and let a second pointer j walk from i to the end. Each time j moves, the subarray [i..j] grows by one element, so we add nums[j] to a running sum. That gives every subarray that starts at i. Then move i one step and repeat.

4Building the logic from the example

Start at i = 0

So the best subarray that starts at index 0 has sum 2. Then i moves to 1 and j starts again from 1: [1], [1, −3], [1, −3, 4], … and so on for every start.

Two variables: the running sum and the best sum

The running sum total only knows the sum of the current subarray [i..j]. It can't remember which earlier subarray was the biggest. So we need a second variable, max_sum, that we update after every addition: max_sum = max(max_sum, total). The running sum is reset to 0 for each new start i, so it must be set inside the outer loop, just before the inner loop.

What should max_sum start as?

The teacher asks: zero, −∞, +∞, or a real number from the array?

• +∞ is clearly wrong: nothing would ever beat it.
• 0 looks natural but is wrong. Imagine the array is only [−2]. The only subarray is [−2], so the answer must be −2. Starting at 0, max(0, −2) stays 0 and we'd return a sum that no subarray has.
• nums[0] is right: it is a real subarray's sum (the subarray [nums[0]]). −∞ also works. The teacher uses nums[0] and says −∞ is fine too.

5Approach steps

1. max_sum = nums[0].
2. For each start i: set total = 0.
3. For each end j from i to n − 1: total += nums[j], then max_sum = max(max_sum, total).
4. After both loops, return max_sum.

6Code (Python)

class Solution:
    def maxSubArray(self, nums):
        n = len(nums)
        max_sum = nums[0]                 # a real subarray's sum (or float('-inf'))
        for i in range(n):                # start of the subarray
            total = 0                     # fresh sum for this start
            for j in range(i, n):         # end of the subarray
                total += nums[j]          # total = sum(nums[i..j])
                max_sum = max(max_sum, total)
        return max_sum

7Code line by line

8Dry run (hand table)

nums = [−2, 1, −3, 4, −1, 2, 1, −5, 4]. One row per start i.

Final answer: 6 ✓, from start 3 to end 6: [4, −1, 2, 1].

9Complexity & remember

• Time O(n²): for the first start the inner loop runs about n times, then n − 1, then n − 2, … That adds up to about n²/2, which is O(n²). With n = 10⁵ that's about 10¹⁰ → TLE. The teacher's code passed the sample tests but got TLE on submit, as she expected.
• Space O(1): two variables.

Part B · Optimal: Kadane's algorithm

LeetCode 53

1The question again, with the new goal

Same question. The goal now is O(n): one pass over the array, with no restarting from every start.

2Choosing the pattern (the teacher's reasoning)

• Two pointers ✗: it needs sorted input, so that every comparison tells you which end to shift. This array isn't sorted, and sorting would destroy the subarrays.
• Sliding window ✗: it can find a best subarray sum, but only with positive numbers. The constraints allow negatives, so it fails (see Part 0 for why).
• Prefix sum ✗: it's for answering many "sum of this range" queries. We need a single maximum.
• Kadane's ✓: built exactly for "maximum subarray sum when negatives can appear".

3Intuition: a negative past only hurts the future

The teacher's tiny example: [−2, 5]. If we keep the −2 and add 5, we get 3. If we drop the −2 and start at 5, we get 5. Carrying a negative sum forward always makes the future total smaller. So:

4Building the logic from the example

nums = [−2, 1, −3, 4, −1, 2, 1, −5, 4].

Index 0: why the best answer starts at nums[0]

The running sum becomes −2. If the array were just [−2], the answer would be −2, so the best answer starts as nums[0] = −2 (same reason as in Part A). Now the running sum −2 is negative. Carrying it would only lower whatever comes next, so we reset it to 0 and move on.

Index 1 and 2: the second reset

Add 1: running sum 1, bigger than −2, so best = 1. Add −3: running sum −2. Negative again → reset to 0.

Index 3: a new start

Add 4: running sum 4, best = 4. Looking only at [−2, 1, −3, 4], the best subarray really is [4], so far so good.

Index 4: the sum went down, but we do NOT reset

Add −1: the running sum drops from 4 to 3. Should we drop it? The teacher says no. It went down, but it is still positive. Look ahead: the next number is 2. Keeping the run gives 4 − 1 + 2 = 5. If we had restarted, we would only get 2 (or keep the old 4). Both are less than 5. A positive running sum still helps the future, even if it shrank.

The rest

Add 2: 5, best = 5. Add 1: 6, best = 6. Add −5: 1. Still positive, keep it. Add 4: 5, not better than 6. Done: 6, in a single loop.

Why the order "update best, then reset" matters

5Approach steps

1. max_sum = nums[0], cur = 0.
2. For each number x: cur += x.
3. max_sum = max(max_sum, cur).
4. If cur < 0: cur = 0 (start fresh next time).
5. Return max_sum.

6Code (Python)

class Solution:
    def maxSubArray(self, nums):
        max_sum = nums[0]                 # best answer so far
        cur = 0                           # running sum of the current run
        for x in nums:
            cur += x                      # extend the run with x
            max_sum = max(max_sum, cur)   # record FIRST
            if cur < 0:                   # a negative past only hurts
                cur = 0                   # start fresh at the next index
        return max_sum

class Solution:
    def maxSubArray(self, nums):
        cur = best = nums[0]              # best subarray ending at index 0
        for x in nums[1:]:
            cur = max(x, cur + x)         # start fresh at x, or extend
            best = max(best, cur)
        return best

7Code line by line

8Dry run (hand table)

nums = [−2, 1, −3, 4, −1, 2, 1, −5, 4], max_sum starts at −2, cur at 0.

The array at three key moments. Yellow = the current run, grey = thrown away, L = where the run started, R = index i.

Final answer: 6 ✓, the same as the brute force.

All-negative check, nums = [−3, −1, −2]: cur −3 → best −3, reset · cur −1 → best −1, reset · cur −2 → best stays −1, reset. Answer −1, the largest single number ✓.

9Complexity & remember

• Time O(n): a single loop, and each number is handled once with a few constant-time steps.
• Space O(1): two variables.

She submitted it and it beat about 99%.

Part C · Revision page

s = Solution()
print(s.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # 6
print(s.maxSubArray([1]))                               # 1
print(s.maxSubArray([5, 4, -1, 7, 8]))                  # 23 (the whole array)
print(s.maxSubArray([-3, -1, -2]))                      # -1 (all negative)
print(s.maxSubArray([-2, 5]))                           # 5  (drop the -2)
print(s.maxSubArray([0, -1, 0]))                        # 0

Based on this video: Maximum Subarray | Kadane's Algorithm