Kadane's Algorithm (Maximum Subarray)

DSA · Classic Algorithms

Theory

Kadane's algorithm finds the contiguous subarray with the largest sum in a single pass. As it scans the array it keeps two values: the best sum of a subarray ending at the current position, and the best sum seen anywhere so far. At each element it decides whether to extend the previous subarray or start fresh from the current element: current = max(x, current + x). If the running sum becomes negative, carrying it forward can only hurt, so starting again is better. The overall answer is the maximum current value seen. This runs in O(n) time and O(1) space, compared with O(n^2) for checking every subarray. Tracking where each restart happens also gives the start and end indexes of the best subarray.

Why we use it

Maximum subarray appears directly in interviews and in practice for finding the best period of profit, the strongest signal segment, or the most active window in a time series.

When to use it

Use it whenever you need the maximum (or, with a sign change, minimum) sum of a contiguous range. For non-contiguous selections, other techniques apply.

How it works

  1. current = best = arr[0]
  2. For each next x
  3. x > current + x? Yes: Start new subarray at x. No: Extend: current += x.
  4. best = max(best, current)
  5. Return best

Syntax

current = best = a[0]
for x in a[1:]:
    current = max(x, current + x)
    best = max(best, current)
Time O(n)   Space O(1)

Example

def max_subarray(nums):
    current = best = nums[0]
    start = best_start = best_end = 0
    for i in range(1, len(nums)):
        if nums[i] > current + nums[i]:
            current, start = nums[i], i
        else:
            current += nums[i]
        if current > best:
            best, best_start, best_end = current, start, i
    return best, nums[best_start:best_end + 1]

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([-3, -1, -2]))

# Daily profit/loss of a shop: best consecutive period
daily = [1200, -800, 300, 1500, -200, -2500, 900, 1100, -100]
best, period = max_subarray(daily)
print("Best period total:", best, "days:", period)

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic