8.05Beginner / Intermediate7 topics20 min7 interactive animations

Subarrays and subsequences

Subarrays are contiguous slices; subsequences keep order but may skip; subsets ignore order. This lesson counts them, sums all subarrays two ways, solves maximum subarray with Kadane's algorithm and counts subarrays with a target sum using prefix sums and a hash map.

Learning goals

Distinguish subarrays, subsequences and subsets and count each
Sum all subarrays by enumeration and by contribution
Apply Kadane's algorithm
Count subarrays with sum k, including negatives

Prerequisites

One-dimensional patternsSummations

8.05.1

Contiguous subarray

A subarray is a contiguous slice a[i..j]. An array of length n has n(n + 1)/2 non-empty subarrays: one for each choice of start i ≤ end j. Enumerating them is the brute force for many problems and costs O(n²) subarrays (O(n³) if you recompute each sum).

Keep a running sum for each start to avoid the third loop.

Java

1int n = a.length;
2for (int i = 0; i < n; i++) {
3    long running = 0;
4    for (int j = i; j < n; j++) {
5        running += a[j];            // sum of a[i..j] in O(1)
6    }
7}

Sum of all subarrays: brute force vs contribution

Interactive · edit the input

int[] arr · length 4

-1

0123

Current subarray endInside the subarrayStart already done

Setup

There are n(n + 1)/2 = 10 subarrays. Fix the start i, extend the end j and keep a running sum.

Step 1 / 12

Java

1static long sumOfAllSubarrays(int[] a) {
2    long total = 0;
3    for (int i = 0; i < a.length; i++) {
4        long running = 0;
5        for (int j = i; j < a.length; j++) {
6            running += a[j];
7            total += running;              // sum of a[i..j]
8        }
9    }
10    return total;
11}
12// O(n): a[i] lies in (i + 1) * (n - i) subarrays
13static long byContribution(int[] a) {
14    long total = 0;
15    for (int i = 0; i < a.length; i++) total += (long) a[i] * (i + 1) * (a.length - i);
16    return total;
17}

Live state

0 subarrays

total

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L2	total=0	There are n(n + 1)/2 = 10 subarrays. Fix the start i, extend the end j and keep a running sum.
2	L7	i=0 j=0 running=3 total=3	a[0..0] sums to 3. Total so far 3 over 1 subarray.
3	L7	i=0 j=1 running=2 total=5	a[0..1] sums to 2. Total so far 5 over 2 subarrays.
4	L7	i=0 j=2 running=6 total=11	a[0..2] sums to 6. Total so far 11 over 3 subarrays.
5	L7	i=0 j=3 running=8 total=19	a[0..3] sums to 8. Total so far 19 over 4 subarrays.
6	L7	i=1 j=1 running=-1 total=18	a[1..1] sums to -1. Total so far 18 over 5 subarrays.
7	L7	i=1 j=2 running=3 total=21	a[1..2] sums to 3. Total so far 21 over 6 subarrays.
8	L7	i=1 j=3 running=5 total=26	a[1..3] sums to 5. Total so far 26 over 7 subarrays.
9	L7	i=2 j=2 running=4 total=30	a[2..2] sums to 4. Total so far 30 over 8 subarrays.
10	L7	i=2 j=3 running=6 total=36	a[2..3] sums to 6. Total so far 36 over 9 subarrays.
11	L7	i=3 j=3 running=2 total=38	a[3..3] sums to 2. Total so far 38 over 10 subarrays.
12	L10	return=38	Total 38 after visiting 10 subarrays: O(n²). The contribution method gets the same answer in O(n).

8.05.2

Subsequences

A subsequence keeps the original order but may skip elements, so the picks need not be adjacent. An array of length n has 2ⁿ subsequences (each element is in or out), including the empty one. Dynamic programming handles problems like the longest increasing subsequence without listing them.

Enumerating subsets with a bitmask lists them all; each mask is one subsequence.

Of [a, b, c]	Count	Examples
Subarrays (non-empty)	6	[a], [a, b], [a, b, c], [b], [b, c], [c]
Subsequences (with empty)	8	[], [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c]

Enumerate all subsets with a bitmask

Interactive · edit the input

int[] arr · length 3

012

In the subset (bit is 1)

subsets so far

empty

Setup

3 items give 2^3 = 8 subsets. Every number from 0 to 7 is one choice: bit i says whether item i is in.

Step 1 / 10

Java

1int n = items.length;
2for (int mask = 0; mask < (1 << n); mask++) {
3    List<Integer> subset = new ArrayList<>();
4    for (int i = 0; i < n; i++) {
5        if ((mask & (1 << i)) != 0) {      // is bit i set?
6            subset.add(items[i]);
7        }
8    }
9    print(subset);
10}

Live state

0 subsets

2^n

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	n=3 2^n=8	3 items give 2^3 = 8 subsets. Every number from 0 to 7 is one choice: bit i says whether item i is in.
2	L5	mask=0 subset={}	mask 0 has no bits set: the empty subset.
3	L5	mask=1 subset={5}	mask 1 = 001 in binary. Bits 0 are set, so the subset is {5}.
4	L5	mask=2 subset={7}	mask 2 = 010 in binary. Bits 1 are set, so the subset is {7}.
5	L5	mask=3 subset={5, 7}	mask 3 = 011 in binary. Bits 0, 1 are set, so the subset is {5, 7}.
6	L5	mask=4 subset={9}	mask 4 = 100 in binary. Bits 2 are set, so the subset is {9}.
7	L5	mask=5 subset={5, 9}	mask 5 = 101 in binary. Bits 0, 2 are set, so the subset is {5, 9}.
8	L5	mask=6 subset={7, 9}	mask 6 = 110 in binary. Bits 1, 2 are set, so the subset is {7, 9}.
9	L5	mask=7 subset={5, 7, 9}	mask 7 = 111 in binary. Bits 0, 1, 2 are set, so the subset is {5, 7, 9}.
10	L10	subsets=8	8 subsets generated in O(2^n · n). This only works for small n (up to about 20-25), because the count doubles with every item.

8.05.3

Subsets

A subset ignores order: {a, c} and {c, a} are the same subset. For a set of n distinct values there are 2ⁿ subsets, which is why exhaustive subset search only works for n up to about 20. A bitmask from 0 to 2ⁿ - 1 enumerates them: bit i says whether element i is included.

Choose your own array and step through the masks.

Java

1int n = a.length;
2for (int mask = 0; mask < (1 << n); mask++) {
3    long sum = 0;
4    for (int i = 0; i < n; i++) if ((mask >> i & 1) == 1) sum += a[i];
5}

Enumerate all subsets with a bitmask

Interactive · edit the input

int[] arr · length 3

012

In the subset (bit is 1)

subsets so far

empty

Setup

3 items give 2^3 = 8 subsets. Every number from 0 to 7 is one choice: bit i says whether item i is in.

Step 1 / 10

Java

1int n = items.length;
2for (int mask = 0; mask < (1 << n); mask++) {
3    List<Integer> subset = new ArrayList<>();
4    for (int i = 0; i < n; i++) {
5        if ((mask & (1 << i)) != 0) {      // is bit i set?
6            subset.add(items[i]);
7        }
8    }
9    print(subset);
10}

Live state

0 subsets

2^n

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	n=3 2^n=8	3 items give 2^3 = 8 subsets. Every number from 0 to 7 is one choice: bit i says whether item i is in.
2	L5	mask=0 subset={}	mask 0 has no bits set: the empty subset.
3	L5	mask=1 subset={5}	mask 1 = 001 in binary. Bits 0 are set, so the subset is {5}.
4	L5	mask=2 subset={7}	mask 2 = 010 in binary. Bits 1 are set, so the subset is {7}.
5	L5	mask=3 subset={5, 7}	mask 3 = 011 in binary. Bits 0, 1 are set, so the subset is {5, 7}.
6	L5	mask=4 subset={9}	mask 4 = 100 in binary. Bits 2 are set, so the subset is {9}.
7	L5	mask=5 subset={5, 9}	mask 5 = 101 in binary. Bits 0, 2 are set, so the subset is {5, 9}.
8	L5	mask=6 subset={7, 9}	mask 6 = 110 in binary. Bits 1, 2 are set, so the subset is {7, 9}.
9	L5	mask=7 subset={5, 7, 9}	mask 7 = 111 in binary. Bits 0, 1, 2 are set, so the subset is {5, 7, 9}.
10	L10	subsets=8	8 subsets generated in O(2^n · n). This only works for small n (up to about 20-25), because the count doubles with every item.

8.05.4

Sum of subarrays

The sum of all subarray sums can be computed in O(n) by contribution: element a[i] belongs to (i + 1) choices of start and (n - i) choices of end, so it appears in (i + 1)(n - i) subarrays. Summing a[i] × (i + 1) × (n - i) over all i gives the total without enumeration.

Switch the method between enumeration and contribution and compare the totals.

Java

1static long sumOfAllSubarrays(int[] a) {
2    long total = 0;
3    int n = a.length;
4    for (int i = 0; i < n; i++) total += (long) a[i] * (i + 1) * (n - i);
5    return total;
6}

Sum of all subarrays: brute force vs contribution

Interactive · edit the input

int[] arr · length 4

-1

0123

Current subarray endInside the subarrayStart already done

Setup

There are n(n + 1)/2 = 10 subarrays. Fix the start i, extend the end j and keep a running sum.

Step 1 / 12

Java

1static long sumOfAllSubarrays(int[] a) {
2    long total = 0;
3    for (int i = 0; i < a.length; i++) {
4        long running = 0;
5        for (int j = i; j < a.length; j++) {
6            running += a[j];
7            total += running;              // sum of a[i..j]
8        }
9    }
10    return total;
11}
12// O(n): a[i] lies in (i + 1) * (n - i) subarrays
13static long byContribution(int[] a) {
14    long total = 0;
15    for (int i = 0; i < a.length; i++) total += (long) a[i] * (i + 1) * (a.length - i);
16    return total;
17}

Live state

0 subarrays

total

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L2	total=0	There are n(n + 1)/2 = 10 subarrays. Fix the start i, extend the end j and keep a running sum.
2	L7	i=0 j=0 running=3 total=3	a[0..0] sums to 3. Total so far 3 over 1 subarray.
3	L7	i=0 j=1 running=2 total=5	a[0..1] sums to 2. Total so far 5 over 2 subarrays.
4	L7	i=0 j=2 running=6 total=11	a[0..2] sums to 6. Total so far 11 over 3 subarrays.
5	L7	i=0 j=3 running=8 total=19	a[0..3] sums to 8. Total so far 19 over 4 subarrays.
6	L7	i=1 j=1 running=-1 total=18	a[1..1] sums to -1. Total so far 18 over 5 subarrays.
7	L7	i=1 j=2 running=3 total=21	a[1..2] sums to 3. Total so far 21 over 6 subarrays.
8	L7	i=1 j=3 running=5 total=26	a[1..3] sums to 5. Total so far 26 over 7 subarrays.
9	L7	i=2 j=2 running=4 total=30	a[2..2] sums to 4. Total so far 30 over 8 subarrays.
10	L7	i=2 j=3 running=6 total=36	a[2..3] sums to 6. Total so far 36 over 9 subarrays.
11	L7	i=3 j=3 running=2 total=38	a[3..3] sums to 2. Total so far 38 over 10 subarrays.
12	L10	return=38	Total 38 after visiting 10 subarrays: O(n²). The contribution method gets the same answer in O(n).

8.05.5

Max/min subarray

The maximum-sum subarray problem asks for the contiguous slice with the largest sum; the minimum version is the same with the signs flipped (negate the values, or keep a running minimum). Brute force is O(n²) with running sums; Kadane's algorithm solves it in O(n).

Run Kadane on your own array: a single negative value or an all-negative array are the interesting cases.

Java

1static int minSubarray(int[] a) {          // same idea as Kadane, tracking the minimum
2    int cur = a[0], best = a[0];
3    for (int i = 1; i < a.length; i++) {
4        cur = Math.min(a[i], cur + a[i]);
5        best = Math.min(best, cur);
6    }
7    return best;
8}

Maximum subarray (Kadane's invariant)

Interactive · edit the input

int[] arr · length 9

-2

-3

-1

-5

012345678

Being comparedBest run ending hereBest subarray so far

Setup

Invariant: after processing index i, current is the best sum of a subarray ending exactly at i, and best is the best sum anywhere in arr[0..i].

Step 1 / 14

Java

1public static int maxSubarray(int[] arr) {
2    int current = arr[0], best = arr[0];          // current = best sum of a run ending at i
3    for (int i = 1; i < arr.length; i++) {
4        current = Math.max(arr[i], current + arr[i]);   // extend the run or restart at i
5        best = Math.max(best, current);
6    }
7    return best;
8}

Live state

0 steps

current

-2

best

-2

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L2	current=-2 best=-2	Invariant: after processing index i, current is the best sum of a subarray ending exactly at i, and best is the best sum anywhere in arr[0..i].
2	L4	i=1 arr[i]=1 current=1 best=-2	Restart at 1: the run before it had a negative sum and would only drag 1 down.
3	L5	i=1 current=1 best=1	New best 1, subarray [1..1].
4	L4	i=2 arr[i]=-3 current=-2 best=1	Extend the run [1..2] to sum -2.
5	L4	i=3 arr[i]=4 current=4 best=1	Restart at 3: the run before it had a negative sum and would only drag 4 down.
6	L5	i=3 current=4 best=4	New best 4, subarray [3..3].
7	L4	i=4 arr[i]=-1 current=3 best=4	Extend the run [3..4] to sum 3.
8	L4	i=5 arr[i]=2 current=5 best=4	Extend the run [3..5] to sum 5.
9	L5	i=5 current=5 best=5	New best 5, subarray [3..5].
10	L4	i=6 arr[i]=1 current=6 best=5	Extend the run [3..6] to sum 6.
11	L5	i=6 current=6 best=6	New best 6, subarray [3..6].
12	L4	i=7 arr[i]=-5 current=1 best=6	Extend the run [3..7] to sum 1.
13	L4	i=8 arr[i]=4 current=5 best=6	Extend the run [3..8] to sum 5.
14	L7	return=6	return 6 from [3..6]. The invariant held at every step, which is the whole correctness proof. O(n), O(1) space.

8.05.6

Kadane's algorithm

Kadane's algorithm keeps the best sum of a subarray ending at the current index: cur = max(a[i], cur + a[i]). Extending the previous run is only worthwhile if it is positive; otherwise start fresh at a[i]. The answer is the largest cur seen. One pass, O(1) space.

Initialise cur and best from the first element, not from 0, so all-negative arrays return the largest (least negative) value.

Java

1static int maxSubarray(int[] a) {
2    int cur = a[0], best = a[0];
3    for (int i = 1; i < a.length; i++) {
4        cur = Math.max(a[i], cur + a[i]);   // extend the run, or restart here
5        best = Math.max(best, cur);
6    }
7    return best;
8}

Maximum subarray (Kadane's invariant)

Interactive · edit the input

int[] arr · length 9

-2

-3

-1

-5

012345678

Being comparedBest run ending hereBest subarray so far

Setup

Invariant: after processing index i, current is the best sum of a subarray ending exactly at i, and best is the best sum anywhere in arr[0..i].

Step 1 / 14

Java

1public static int maxSubarray(int[] arr) {
2    int current = arr[0], best = arr[0];          // current = best sum of a run ending at i
3    for (int i = 1; i < arr.length; i++) {
4        current = Math.max(arr[i], current + arr[i]);   // extend the run or restart at i
5        best = Math.max(best, current);
6    }
7    return best;
8}

Live state

0 steps

current

-2

best

-2

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L2	current=-2 best=-2	Invariant: after processing index i, current is the best sum of a subarray ending exactly at i, and best is the best sum anywhere in arr[0..i].
2	L4	i=1 arr[i]=1 current=1 best=-2	Restart at 1: the run before it had a negative sum and would only drag 1 down.
3	L5	i=1 current=1 best=1	New best 1, subarray [1..1].
4	L4	i=2 arr[i]=-3 current=-2 best=1	Extend the run [1..2] to sum -2.
5	L4	i=3 arr[i]=4 current=4 best=1	Restart at 3: the run before it had a negative sum and would only drag 4 down.
6	L5	i=3 current=4 best=4	New best 4, subarray [3..3].
7	L4	i=4 arr[i]=-1 current=3 best=4	Extend the run [3..4] to sum 3.
8	L4	i=5 arr[i]=2 current=5 best=4	Extend the run [3..5] to sum 5.
9	L5	i=5 current=5 best=5	New best 5, subarray [3..5].
10	L4	i=6 arr[i]=1 current=6 best=5	Extend the run [3..6] to sum 6.
11	L5	i=6 current=6 best=6	New best 6, subarray [3..6].
12	L4	i=7 arr[i]=-5 current=1 best=6	Extend the run [3..7] to sum 1.
13	L4	i=8 arr[i]=4 current=5 best=6	Extend the run [3..8] to sum 5.
14	L7	return=6	return 6 from [3..6]. The invariant held at every step, which is the whole correctness proof. O(n), O(1) space.

8.05.7

Counting subarrays

To count subarrays whose sum equals k, use prefix sums: a[l..r] sums to k when prefix[r + 1] - prefix[l] = k. Scan once, and for each prefix look up how many earlier prefixes equal prefix - k in a hash map. This works with negative numbers, where a sliding window does not. O(n) time and space.

Seed the map with the empty prefix (0 seen once) so subarrays that start at index 0 are counted.

Java

1static int countSubarraysWithSum(int[] a, int k) {
2    Map<Integer, Integer> seen = new HashMap<>();
3    seen.put(0, 1);
4    int prefix = 0, count = 0;
5    for (int x : a) {
6        prefix += x;
7        count += seen.getOrDefault(prefix - k, 0);
8        seen.merge(prefix, 1, Integer::sum);
9    }
10    return count;
11}

Count subarrays with sum k (prefix sums + hash map)

Interactive · edit the input

int[] arr · length 6

-3

012345

Current elementEnds a matching subarrayProcessed

seen: prefix → times

0:1

Setup

A subarray a[l..r] has sum k exactly when prefix[r + 1] - prefix[l] = k. Remember how often each prefix has occurred.

Step 1 / 14

Java

1static int countSubarraysWithSum(int[] a, int k) {
2    Map<Integer, Integer> seen = new HashMap<>();
3    seen.put(0, 1);                              // the empty prefix
4    int prefix = 0, count = 0;
5    for (int x : a) {
6        prefix += x;
7        count += seen.getOrDefault(prefix - k, 0);   // earlier prefixes that leave sum k
8        seen.merge(prefix, 1, Integer::sum);
9    }
10    return count;
11}

Live state

prefix

count

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L3	prefix=0 count=0 k=3	A subarray a[l..r] has sum k exactly when prefix[r + 1] - prefix[l] = k. Remember how often each prefix has occurred.
2	L7	i=0 prefix=1 need=-2 hits=0 count=0	Nothing ending at 0 has prefix -2 before it: no new match.
3	L8	i=0 prefix=1 count=0	Record prefix 1 (now seen 1 time).
4	L7	i=1 prefix=3 need=0 hits=1 count=1	prefix 3 - k 3 = 0 was seen 1 time, so 1 subarray ending at 1 sum to 3. Count = 1.
5	L8	i=1 prefix=3 count=1	Record prefix 3 (now seen 1 time).
6	L7	i=2 prefix=6 need=3 hits=1 count=2	prefix 6 - k 3 = 3 was seen 1 time, so 1 subarray ending at 2 sum to 3. Count = 2.
7	L8	i=2 prefix=6 count=2	Record prefix 6 (now seen 1 time).
8	L7	i=3 prefix=3 need=0 hits=1 count=3	prefix 3 - k 3 = 0 was seen 1 time, so 1 subarray ending at 3 sum to 3. Count = 3.
9	L8	i=3 prefix=3 count=3	Record prefix 3 (now seen 2 times).
10	L7	i=4 prefix=4 need=1 hits=1 count=4	prefix 4 - k 3 = 1 was seen 1 time, so 1 subarray ending at 4 sum to 3. Count = 4.
11	L8	i=4 prefix=4 count=4	Record prefix 4 (now seen 1 time).
12	L7	i=5 prefix=5 need=2 hits=0 count=4	Nothing ending at 5 has prefix 2 before it: no new match.
13	L8	i=5 prefix=5 count=4	Record prefix 5 (now seen 1 time).
14	L10	return=4	4 subarrays sum to 3. One pass, O(n) time and space; negative numbers are fine, unlike a sliding window.

Practice ladder

Now try it yourself

Easy

List all subarrays of {1, 2, 3}
How many subsequences does an array of 5 elements have?

Medium

Find the maximum subarray sum of {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Count subarrays of {1, 1, 1} with sum 2

Advanced

Return the start and end of the maximum subarray as well as its sum

Key takeaways

Subarrays are n(n + 1)/2, subsequences and subsets are 2ⁿ.
Contribution counting turns O(n²) into O(n) for sums over all subarrays.
Kadane: cur = max(a[i], cur + a[i]); prefix sums plus a hash map count subarrays with a target sum.