Problem overview
The method maxSumOfThreeSubarrays receives an array nums of integers and must pick three non-overlapping, non-empty subarrays, one after another, so that their sums add up to the largest possible total. It returns that total. The array has at least three numbers, and the values can be negative.
In the example, nums = [2, 3, -8, 7, -2, 9, -9, 7, -2, 4]. The subarrays [2, 3], [7, -2, 9] and [7, -2, 4] sum to 5, 14 and 9, so the answer is 28. The -8 and the -9 between them are left out, because including either would only lower the total.
Approach: fix the middle subarray, then use the best left and right parts
Choosing three subarrays directly means choosing six boundaries, which is a lot of loops. A smaller search comes from looking at the middle subarray. Once its first index i and last index j are fixed, the other two choices are independent of each other:
- the first subarray must lie inside
nums[0..i - 1], so the best one is the maximum subarray sum of that prefix; - the third subarray must lie inside
nums[j + 1..n - 1], so the best one is the maximum subarray sum of that suffix.
The answer for this middle subarray is the best prefix sum plus the middle sum plus the best suffix sum. Trying every pair i, j and keeping the largest total gives the result.
The maximum subarray sum of a piece of the array comes from Kadane's algorithm, which this lesson reuses as a helper, maxSumSubarray. This version calls it again for every pair of middle boundaries, which is simple but slow. The other lessons on this problem precompute the best prefix and suffix sums so the helper is not repeated; this one is the brute-force starting point.
Step by step
- Store the length in
n, since the loops use it many times. - Start
maxSumatNumber.NEGATIVE_INFINITY. The answer can be negative when all the numbers are, so starting at 0 would return a value that no choice of subarrays produces. Negative infinity is lower than any real total. - Loop
ifrom 1 ton - 1. It is the first index of the middle subarray. It starts at 1 so that the first subarray,nums[0..i - 1], has at least one element. Ati = n - 1there is no room for a third subarray, but the inner loop simply doesn't run. - Compute
sum1asthis.maxSumSubarray(nums.slice(0, i)). The helper is a method, so it is called throughthis.slice(0, i)copies the elements from index 0 up to, but not including,i. - Start
sum2at 0 inside the outer loop. It is the sum of the middle subarray, and each newibegins a new one. - Loop
jfromiton - 2. It is the last index of the middle subarray. Stopping atn - 2leaves at least one element for the third subarray. - Add
nums[j]tosum2. Movingjone step right extends the middle subarray by one element, so there is no need to add up the whole range again. - Compute
sum3as the maximum subarray sum ofnums.slice(j + 1). With only a start index,slicegoes to the end of the array. - Update
maxSumwithMath.max(maxSum, sum1 + sum2 + sum3). - Return
maxSumafter the outer loop. - Write
maxSumSubarray.resultis the best sum found so far and starts atnums[0], not 0, because every number might be negative.maxSumis the best sum of a subarray ending at the current element. For eachval, that subarray either extends the previous one, when the previous sum is positive, or starts fresh atval. That isval + Math.max(maxSum, 0). Thenresultkeeps the larger of itself andmaxSum.
The solution in TypeScript
class Solution {
maxSumSubarray(nums: number[]): number {
let result = nums[0];
let maxSum = 0;
for (let val of nums) {
maxSum = val + Math.max(maxSum, 0);
result = Math.max(result, maxSum);
}
return result;
}
maxSumOfThreeSubarrays(nums: number[]): number {
let n = nums.length;
let maxSum = Number.NEGATIVE_INFINITY;
for (let i = 1; i < n; i++) {
let sum1 = this.maxSumSubarray(nums.slice(0, i));
let sum2 = 0;
for (let j = i; j < n - 1; j++) {
sum2 += nums[j];
let sum3 = this.maxSumSubarray(nums.slice(j + 1));
maxSum = Math.max(maxSum, sum1 + sum2 + sum3);
}
}
return maxSum;
}
}
The TypeScript details worth knowing:
slicecopies.nums.slice(0, i)returns a new array and leavesnumsalone. The end index is excluded, soslice(0, 3)on[2, 3, -8, 7]gives[2, 3, -8]. That copying is part of the cost of this version.thisis required. Inside a class,maxSumSubarray(...)on its own refers to no variable. Methods are reached through the object, so the call isthis.maxSumSubarray(...).Number.NEGATIVE_INFINITYis a realnumber. It fits thenumbertype, compares correctly with any sum, and is replaced by the first candidate total. All numbers in TypeScript are doubles, so sums don't wrap around the way fixed-size integers would.- The annotations are inferred.
let result = nums[0]is anumberwithout being told. The parameter and return types on the methods are the only annotations the code needs.
Complexity
Time: O(n³). The two loops visit about n²/2 pairs (i, j). For each pair, slice(j + 1) and the helper both walk up to n elements, and so does the first call per i. The work per pair is O(n), so the total is cubic. Doubling the array length makes the code about eight times slower.
Space: O(n). The slices are the only extra memory: each one holds up to n elements, and a slice is dropped once the helper returns.
Edge cases and common mistakes
- All numbers negative. For
[-5, -1, -3, -2]the answer is-6, from the single-element subarrays[-1],[-3]and[-2]. StartingmaxSumat 0 would return 0, which no valid choice produces. - Exactly three numbers.
[1, 2, 3]returns 6: each subarray is a single element. Onlyi = 1andj = 1are possible. - Helper starting value. If
resultinmaxSumSubarraystarted at 0, a negative-only piece would report 0 instead of its largest element. - Loop bounds. Letting
jreachn - 1would call the helper with an empty array, andnums[0]of an empty array isundefined, which poisons the sums withNaN. - Forgetting to reset
sum2. It must start at 0 for everyi, or the middle sum carries over from the previous start.
Testing
[2, 3, -8, 7, -2, 9, -9, 7, -2, 4]gives28.[-5, -1, -3, -2]gives-6.[1, 2, 3]gives6.[-1, -2, -3]gives-6.