Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Kadane's Algorithm

Best subarray ending here is either extend or restart.

time O(n)space O(1)

What it is

A tiny dynamic program: the best sum of a subarray ending at i is max(a[i], best_ending_here + a[i]). Track the best over all i. It replaces the O(n²) or O(n³) enumeration of subarrays.

When to reach for it

  • Maximum sum contiguous subarray
  • Best profit from a single run
  • Optimal choice depends only on the previous state

Clues in the problem

  • Contiguous and sum-maximizing
  • Negative numbers present

Template

def max_subarray(a):
cur = best = a[0]
for x in a[1:]:
cur = max(x, cur + x) # extend or restart
best = max(best, cur)
return best

Practice problems

  • Maximum Subarray
  • Maximum Product Subarray
  • Best Time to Buy and Sell Stock
  • Maximum Sum Circular Subarray

Common mistakes

  • Initializing best to 0, which breaks all-negative arrays
  • Not tracking indices when the range is required