Vinay C.
Data Structures & Algorithms10 min read

Maximum subarray (Kadane)

Lesson 7.4 · Medium · Extend or restart · 10 min · by Vinay C

We'll cover the following

Find the contiguous subarray with the largest sum.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

16 items · 17 steps
start/i-10
51
-72
-33
84
45
-66
-17
28
19
710
-311
-512
-313
314
-315

Start with -1. Running sum is now -1.

cur -1 · best -1

1 / 17

The idea

Complexity

TimeSpaceWhy
O(n)O(1)One pass with a running sum and a best-so-far.

In Python

def max_subarray(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)      # extend, or restart here
        best = max(best, cur)
    return best
</> Now code it →Try it on LeetCode: Maximum Subarray →

Summary: say it in the interview

  • At each number, either extend the previous run or start fresh here. If the running sum went negative, it can only drag the next numbers down, so restart. Remember the best total seen.
  • Time O(n), space O(1). One pass with a running sum and a best-so-far.