# Kadane's Algorithm — Maximum Subarray Sum in O(n)

Source: https://skills101.in/learn/dsa/dsa-kadanes-algorithm — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-17.

**Problem:** given an array of integers (some may be negative), find the **largest sum** of any **contiguous** subarray. For `[-2, 1, -3, 4, -1, 2, 1, -5, 4]` the answer is `6`, from `[4, -1, 2, 1]`.

Checking every subarray is O(n²) (or O(n³) if you re-add each one). **Kadane's algorithm** does it in a single pass, O(n) time and O(1) memory. It is one of the most asked array questions in placement interviews.

## 1. The idea: extend or restart

Walk left to right and keep `cur` = the **best sum of a subarray that ends exactly here**. At each new element `x` there are only two choices:

- **extend** the previous best subarray: `cur + x`, or
- **restart** a new subarray at `x`: just `x`.

Take the larger: `cur = max(x, cur + x)`. If the sum so far is negative, it can only drag `x` down — so restart. The answer is the largest `cur` ever seen.

![Kadane on -2 1 -3 4 -1 2 1 -5 4: the cur row is -2 1 -2 4 3 5 6 1 5 and the best row is -2 1 1 4 4 5 6 6 6; the best sum 6 comes from the subarray 4 -1 2 1](https://skills101.in/learn-img/dsa/kadane.svg)

```python
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

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

```text
6
23
-1
```

Starting with `cur = best = a[0]` (not 0) handles the **all-negative** case correctly: the answer is the largest single element, `-1`, not `0`. (Some problems allow an empty subarray with sum 0 — read the statement.)

**Why is this correct?** Any best subarray ends somewhere. `cur` at that index is the best sum ending there, because the only way to end at `i` is either `a[i]` alone or "best ending at `i − 1`" plus `a[i]`. That is a tiny **dynamic programming** recurrence that only needs the previous value.

## 2. Returning the subarray itself

Interviewers often follow up with "print the subarray". Remember where the current subarray **started**, and copy the start and end whenever `best` improves.

```python
def max_subarray_with_range(a):
    cur, best = a[0], a[0]
    start = best_l = best_r = 0
    for i in range(1, len(a)):
        if a[i] > cur + a[i]:      # restarting is better
            cur, start = a[i], i
        else:
            cur += a[i]
        if cur > best:
            best, best_l, best_r = cur, start, i
    return best, a[best_l:best_r + 1]

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

```text
(6, [4, -1, 2, 1])
```

### The same in Java

```java
public class Main {
    static long maxSubarray(int[] a) {
        long cur = a[0], best = a[0];
        for (int i = 1; i < a.length; i++) {
            cur = Math.max(a[i], cur + a[i]);
            best = Math.max(best, cur);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxSubarray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(maxSubarray(new int[]{-8, -3, -6}));
    }
}
```

```text
6
-3
```

Using `long` protects against overflow when 10⁵ values of up to 10⁹ are added.

## 3. Variants interviewers ask next

### Maximum circular subarray

The array is a circle, so a subarray may wrap from the end back to the start. The best answer is either a normal subarray (plain Kadane), or a **wrapping** one — which equals `total − (minimum subarray)`. Run Kadane twice: once for the max, once for the min.

```python
def max_circular(a):
    best_max = cur_max = a[0]
    best_min = cur_min = a[0]
    for x in a[1:]:
        cur_max = max(x, cur_max + x); best_max = max(best_max, cur_max)
        cur_min = min(x, cur_min + x); best_min = min(best_min, cur_min)
    if best_max < 0:               # every number negative: wrapping would mean "take nothing"
        return best_max
    return max(best_max, sum(a) - best_min)

print(max_circular([5, -3, 5]))
print(max_circular([-3, -2, -3]))
```

```text
10
-2
```

### Maximum product subarray

With products, a **negative × negative** becomes large. Keep both the largest and the smallest product ending here, and swap them when `x` is negative.

```python
def max_product(a):
    hi = lo = best = a[0]
    for x in a[1:]:
        if x < 0:
            hi, lo = lo, hi
        hi = max(x, hi * x)
        lo = min(x, lo * x)
        best = max(best, hi)
    return best

print(max_product([2, 3, -2, 4]))
print(max_product([-2, 3, -4]))
```

```text
6
24
```

### Buy and sell a stock once

"Maximum profit from one buy and one later sell" is Kadane on the **daily differences** — or simply track the lowest price so far and the best `price − lowest`.

## Common mistakes

- Starting with `best = 0`, which returns 0 for an all-negative array.
- Resetting `cur` to 0 **before** updating `best` — the order of the two lines matters.
- In the circular version, forgetting the all-negative case (`total − min` would be 0 = an empty subarray).
- Using `int` when the sum can exceed about 2.1 × 10⁹.

## Quick recap

- `cur = max(x, cur + x)`: extend the best subarray ending at the previous index, or restart at `x`.
- `best` = the largest `cur` seen; start both at `a[0]`.
- O(n) time, O(1) memory; it is a one-variable dynamic programming solution.
- Circular: `max(kadane, total − min subarray)`; product: track both max and min.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-kadanes-algorithm