Problem overview
The method maxSumOfThreeSubarrays receives an array nums of integers with at least three elements. It must choose three non-empty subarrays that don't overlap, and return the largest possible total of their sums. A subarray is a continuous run of elements.
For nums = [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] the best choice is [2, 3], [7, -2, 9] and [7, -2, 4]. Their sums are 5, 14 and 9, so the answer is 28. Notice that the three subarrays don't have to cover the array: the -8 and the -9 are skipped.
Approach: try every triple of subarrays
This first lesson on the problem uses brute force. A subarray is fixed by its first and last index, and three non-overlapping subarrays in left-to-right order are fixed by six indices:
i1 <= j1 < i2 <= j2 < i3 <= j3
The strict < between a pair and the next one is what keeps the subarrays from overlapping, and the <= inside a pair allows a subarray of one element. The solution loops over all such six-tuples and keeps the largest total. It is slow, but it is easy to trust, and it gives you a reference to compare faster solutions against.
The only cleverness is in the sums. Instead of adding up a subarray from scratch for every end index, each loop that moves the end one step right adds just the one new element to a running sum.
To see the loops at work, take [1, 2, 3, 4]. One of the six-tuples is i1 = 0, j1 = 0, i2 = 1, j2 = 1, i3 = 2, j3 = 3: the subarrays [1], [2] and [3, 4], with sums 1, 2 and 7, total 10. No other triple does better, because the three subarrays together can use at most all four elements, and here all of them are used.
Because the loops only move forward, each triple is visited exactly once, in left-to-right order, and the order of the subarrays never needs to be tried again.
Step by step
- Store the length in
n, since every loop needs it. - Start
maxSumat negative infinity. Every element might be negative, so the best total can be negative, and starting at 0 would report a total that no choice of subarrays reaches.Number.NEGATIVE_INFINITYloses to any real sum. - Choose the first subarray's start with
i1looping over the indices. - Declare
sum1as 0 inside that loop, so every start begins with an empty sum. - Choose its end with
j1, fromi1to the last index. - Add
nums[j1]tosum1. Nowsum1is the sum ofnums[i1..j1]. - Choose the second subarray's start,
i2, strictly afterj1. - Declare
sum2as 0, again inside the loop that picks the start. - Choose its end,
j2, fromi2onwards. - Add
nums[j2]tosum2. - Choose the third subarray's start,
i3, strictly afterj2. - Declare
sum3as 0. - Choose its end,
j3, fromi3onwards. - Add
nums[j3]tosum3. - Compare the total. In the innermost loop, keep the larger of
maxSumandsum1 + sum2 + sum3withMath.max. - Return
maxSumafter the outermost loop ends.
The solution in TypeScript
class Solution {
maxSumOfThreeSubarrays(nums: number[]): number {
const n: number = nums.length;
let maxSum: number = Number.NEGATIVE_INFINITY;
for (let i1 = 0; i1 < n; i1++) {
let sum1 = 0;
for (let j1 = i1; j1 < n; j1++) {
sum1 += nums[j1];
for (let i2 = j1 + 1; i2 < n; i2++) {
let sum2 = 0;
for (let j2 = i2; j2 < n; j2++) {
sum2 += nums[j2];
for (let i3 = j2 + 1; i3 < n; i3++) {
let sum3 = 0;
for (let j3 = i3; j3 < n; j3++) {
sum3 += nums[j3];
maxSum = Math.max(maxSum, sum1 + sum2 + sum3);
}
}
}
}
}
}
return maxSum;
}
}
Some TypeScript details:
- Annotations on initialised variables.
const n: number = nums.length;would infer the same type without the annotation. Writing it is allowed and sometimes helps readers. The compiler erases it, so it has no effect at run time. Number.NEGATIVE_INFINITYis anumber. JavaScript numbers are doubles, which have a value for infinity, somaxSumcan keep the typenumber.Math.max(-Infinity, x)isxfor every finitex.- Nothing overflows. Sums are doubles, and integers are exact up to
Number.MAX_SAFE_INTEGER(2^53 - 1), far beyond what the lesson uses. - Block scope.
sum1,sum2andsum3are declared withletinside the loop that picks the start, so each new start gets a fresh sum.
Complexity
Time: O(n⁶). Six nested loops each run up to n times. Because the indices must satisfy i1 <= j1 < i2 <= j2 < i3 <= j3, the number of combinations is a fraction of n⁶, but it still grows like n⁶. Doubling the array size multiplies the work by about 64, so this is practical only for tiny inputs. Faster solutions to the same problem use prefix sums and the best-so-far idea to avoid most of the loops.
Space: O(1). The method uses a handful of numbers.
Edge cases and common mistakes
- Exactly three elements. Each subarray is one element, so the answer is the sum of the whole array. For
[-1, -2, -3]the answer is-6. - Negative values. For
[-5, -1, -2, -9]the answer is-8, from[-5],[-1]and[-2]. All three subarrays must be non-empty, so you can't improve the total by choosing fewer. - Starting
maxSumat 0. This returns 0 for the all-negative arrays above, and 0 is not the sum of any valid choice. - Letting subarrays touch an index twice. Starting
i2atj1instead ofj1 + 1would let two subarrays share an element and count it twice. - Sharing one sum variable. Declaring
sum2outside thei2loop makes the sum carry over from an earlier start. - Fewer than three elements. The lesson promises at least three. With two elements no choice exists, and this code would return
-Infinity.
Testing
[2, 3, -8, 7, -2, 9, -9, 7, -2, 4]gives28.[-1, -2, -3]gives-6.[-5, -1, -2, -9]gives-8.[1, 2, 3, 4]gives10.