Maximum subarray sum

Kadane's algorithm finds the largest sum of a subarray, a block of consecutive elements of an array (a list of numbers stored in order), in one pass from left to right.

Explanation

A small shop writes down its profit for each day of a 5-day week: 3, 1, −6, 4, 2. A loss is a negative number. Which period of consecutive days earned the most?

A row of five daily profits, 3, 1, −6, 4, 2, numbered days 1 to 5, with a blue bracket under days 4 and 5.

Fig. 1. The most profitable period is outlined in blue.

A week has only 15 periods, so you can check them by eye: the best is days 4–5, with 4 + 2 = 6. The loss on day 3 separates two good runs, days 1–2 with 4 and days 4–5 with 6.

Take 8 days: 2, −3, 4, −1, −2, 1, 5, −3. They already have 36 periods, and $n$ days have $n (n + 1) /2$ n(n+1)/2: 66,795 for a year, about $5 \cdot 1 0^{9}$ 5 \cdot 10^9 for $1 0^{5}$ 10^5 days. At about $1 0^{8}$ 10^8 simple steps per second (a rule of thumb, see time complexity), that is about 50 seconds of additions. We need one walk along the days.

The week suggests a rule: cut at every loss day and keep the best run of profitable days. The runs are day 1 (2), day 3 (4) and days 6–7 (1 + 5 = 6), so the rule answers 6, the red period. But days 3–7 give 4 − 1 − 2 + 1 + 5 = 7, the blue period.

The profits 2, −3, 4, −1, −2, 1, 5, −3 for days 1 to 8, drawn twice: in the top row a red bracket marks days 6–7, the best run without a loss (sum 6); in the bottom row a blue bracket marks days 3–7, the best period (sum 7).

Fig. 2. Red: the best run without a loss. Blue: the best period.

The losses on days 4 and 5 were worth crossing. Day 3 had already earned 4, so the total stayed positive (4 − 1 − 2 = 1), and days 6 and 7 added to it.

So carry the total of the current period while it is positive, because adding a positive amount to the next day's profit only raises it. When the total is negative, drop it and start a new period at the next day, as the week did after day 3 (3 + 1 − 6 = −2). Remember the largest total seen; it is the answer. This is Kadane's algorithm.

Kadane's algorithm on the profits 2, −3, 4, −1, −2, 1, 5, −3, step by step: a pointer marks the current day, a blue bracket the current period, and a lower row fills with the period totals 2, −1, 4, 3, 1, 2, 7, 4, the largest so far outlined.

Day 1: the period is day 1 alone, with total 2. The outlined number is the largest total so far.

1/9

Fig. 3. Step through with the buttons or the arrow keys. The lower row is the total of the current period after each day, and the outlined number is the largest so far.

Each number in the lower row is the total of the period with the largest sum that ends on that day.

Buying and selling once

Many problems give a price for each day and ask for the largest profit from buying once and selling later. For prices 4, 6, 3, 8, 5, buying at 3 on day 3 and selling at 8 on day 4 earns 8 − 3 = 5, which is the change +5 between those days. In general, buying on one day and selling on a later one earns the sum of the day-to-day changes between them. So take the changes (each price minus the one before it), here 2, −3, 5, −3, and find their largest subarray sum. The totals are 2, then −1, which is dropped, then 5 and 2, so the best profit is 5.

Prices 4, 6, 3, 8, 5 for days 1 to 5, with the changes +2, −3, +5, −3 in a row below, each between the two days it connects; a blue bracket marks days 3 and 4 above the +5, and a black bracket groups +2, −3, +5, which add up to 8 − 4 = 4.

Fig. 4. Buying on one day and selling on a later one earns the sum of the changes between them.

If the problem says "print 0 if no profit is possible", an empty subarray is allowed. It means not trading at all and has sum 0, so the answer is never negative. With one price there are no changes, and the answer is 0.

The rectangle with the largest sum

Kadane's algorithm also finds the rectangle with the largest sum in a table of numbers. Fix the top row and the bottom row of the rectangle, and add up each column between them. This gives one array with an entry per column. A rectangle between these rows is a block of consecutive columns, so its sum is a subarray sum of that array, and Kadane's algorithm finds the best one. Do this for every pair of rows and keep the best.

A 3 by 4 table with rows 1, 4, −2, 6; −6, 3, 4, 4; −3, −5, 3, −4. Rows 1 and 2 are shaded, and their columns 2 to 4 are shaded darker. Below the table, the column sums of rows 1 and 2, −5, 7, 2, 10, have a blue bracket under positions 2 to 4.

Fig. 5. Rows 1–2 and their column sums. The blue block is the best rectangle between rows 1 and 2.

The table has 3 rows, so there are 6 pairs:

Rows	Column sums	Best block of columns	Sum
1–1	1, 4, −2, 6	1–4	9
1–2	−5, 7, 2, 10	2–4	19
1–3	−8, 2, 5, 6	2–4	13
2–2	−6, 3, 4, 4	2–4	11
2–3	−9, −2, 7, 0	3	7
3–3	−3, −5, 3, −4	3	3

Rows 1–2 win with 19. For a fixed top row, moving the bottom row down by one adds that row's values to the column sums, so each new array costs $O (m)$ for $m$ columns. With $n$ rows there are about $n^{2} /2$ n^2 / 2 pairs, so the whole search takes $O (n^{2} m)$ O(n^2 m), about $6 \cdot 1 0^{7}$ 6 \cdot 10^7 steps for a $500 \times 500$ 500 \times 500 table:

for (int top = 0; top < n; top++) {
    vector<long long> col(m, 0);
    for (int bottom = top; bottom < n; bottom++) {
        for (int j = 0; j < m; j++) col[j] += t[bottom][j];
        // run Kadane's algorithm on col and keep the largest sum
    }
}

C++

Implementation

In code, the days are an array a of $n \geq 1$ n \ge 1 numbers, indexed from 0. The algorithm is a small dynamic programming solution. Its state is cur: after position i, it is the largest sum of a subarray that ends exactly at a[i], the total of the current period from the explanation. A table e[0..n-1] with one value per position would work too, but each cell reads only the one before it, so one variable is enough. To print where the best subarray is, keep start, where the current subarray began, and copy it into l whenever best grows.

Base case: cur = best = a[0], because the only subarray ending at a[0] is a[0] itself.
Order: i goes from 1 to n - 1, left to right, because each cur needs the one before it.
Transition: if cur < 0, set it to 0 and set start = i; then add a[i].
Answer: if cur > best, remember cur, start and i.

The input has $n$ on the first line and the $n$ numbers on the second. For the 8 days it is:

8
2 -3 4 -1 -2 1 5 -3

The program prints the largest sum, then the first and last positions of the subarray, numbered from 1.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // state and base case
    long long cur = a[0], best = a[0];   // empty subarray allowed: cur = 0, best = 0, and the loop starts at i = 0
    int start = 0, l = 0, r = 0;         // remove if you only need the sum

    // order
    for (int i = 1; i < n; i++) {
        // transition: drop a negative past, then add a[i]
        if (cur < 0) {
            cur = 0;
            start = i;
        }
        cur += a[i];
        // answer
        if (cur > best) {
            best = cur;
            l = start;   // remove these two lines if you only need the sum
            r = i;
        }
    }

    cout << best << '\n';
    cout << l + 1 << ' ' << r + 1 << '\n';   // remove if you only need the sum
}

When an empty subarray is allowed, start with cur = best = 0 and run the loop from i = 0, as the comment says, and print positions only when best > 0. This also works when there are no numbers at all, as with a single price in the buying problem.

The comparisons are strict on purpose. With cur < 0, a total of exactly 0 is kept, so on 2, −2, 3 the program prints positions 1–3; cur <= 0 would print 3–3, a shorter subarray with the same sum. cur > best keeps the first best subarray when there is a tie.

The program looks at each number once, so it takes $O (n)$ time and $O (1)$ memory besides the array.

Which line goes in the gap?

for (int i = 1; i < n; i++) {
    // ???
    cur += a[i];
    if (cur > best) { best = cur; l = start; r = i; }
}

if (cur < 0) { cur = 0; start = i; }

if (a[i] < 0) { cur = 0; start = i; }

if (cur < best) { cur = 0; start = i; }

if (a[i] > cur) { cur = 0; start = i; }

Correctness proof

Let $e_{i}$ e_i be the largest sum of a subarray that ends at position $i$ . Every subarray that ends at $i$ is either $a_{i}$ a_i alone, or a subarray that ends at $i - 1$ i - 1 followed by $a_{i}$ a_i. The best of the second kind is $e_{i - 1} + a_{i}$ e_{i-1} + a_i. So

e_{i} = a_{i} + max (e_{i - 1}, 0),

e_i = a_i + \max(e_{i-1}, 0),

which is what the code computes: it adds the previous cur only if it is not negative. The answer is the largest $e_{i}$ e_i, because every subarray ends at some position $i$ .

Two rows of 8 cells. Top row: the daily profits 2, −3, 4, −1, −2, 1, 5, −3, with a blue bracket under days 3 to 6 and day 7 (profit 5) highlighted. Bottom row: the totals 2, −1, 4, 3, 1, 2, 7, 4, with the totals for day 6 (2) and day 7 (7) outlined.

Fig. 6. The best period ending on day 7 is the best period ending on day 6 (blue, total 2) followed by day 7: 2 + 5 = 7.

Common mistakes

Keeping only the largest sum so far, as in f = max(f, f + a[i], a[i]). It adds a[i] to a subarray that may end earlier, so the numbers are no longer consecutive: on 3, −5, 4 it gives 7 (3 + 4) instead of 4. The state must be the largest sum that ends at a[i].
Cutting at every negative number. On the 8 days it gives 6 instead of 7. Drop the past only when its total is negative.
Updating best before adding today's number, so the last number is never counted. On 1, 2, 3 this prints 3 instead of 6. Add a[i] first, then compare with best.

Similar algorithms

With prefix sums, the sum of a subarray is a difference of two prefix sums, so the best subarray ending at r subtracts the smallest earlier prefix sum from the prefix sum at r. Keeping that smallest prefix sum while walking is also $O (n)$ , and cur equals exactly that difference.

When all numbers are positive and the sum must not exceed a limit $s$ , use two pointers. Kadane's algorithm can't respect the limit, because it only ever drops a negative total, never a positive one that has grown too large.

A segment tree answers the largest subarray sum inside a range $[l, r]$ [l, r] of an array whose values change. Each node keeps the sum, the best prefix, the best suffix and the best subarray of its part.