Problem overview
The method MaxSumOfThreeSubarrays receives an int[] nums with at least three numbers. It must choose three non-empty subarrays that don't overlap, and return the largest possible total of their sums. A subarray is a run of neighbouring elements, so each one is described by a first index and a last index.
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, which gives 28. The negative numbers -8 and -9 sit in the gaps between the chosen subarrays, where they cost nothing.
Approach: try every triple of subarrays
This lesson is the plain brute force. A solution is fully described by six indices: i1 and j1 for the first subarray, i2 and j2 for the second, i3 and j3 for the third. The only constraints are i1 <= j1 < i2 <= j2 < i3 <= j3, which makes the subarrays non-empty, ordered left to right and disjoint. If you try every index combination that obeys them and keep the best total, you can't miss the answer.
Six nested loops follow naturally. Each loop starts just after the end of the previous subarray, which builds the ordering constraint into the loop bounds. The later lessons on this problem remove loops by reusing sums that were already computed, but it's worth writing the version that is obviously correct first.
Growing sums instead of recomputing them
A second detail keeps the code from being even slower. When j1 moves one step to the right, the first subarray gains exactly one element, so sum1 only needs nums[j1] added. The same holds for sum2 and sum3. Each sum is reset to 0 when its start index changes and grows as its end index moves.
Step by step
- Store the length.
nums.Lengthappears in every loop condition, so it goes into a localn. - Start the answer very low.
maxSumbegins atint.MinValue. If every number is negative, the answer is negative too, so starting at 0 would return a total that no choice of subarrays can produce. - Pick the first subarray. The outer loop over
i1chooses its start.sum1is declared inside that loop and starts at 0. The loop overj1, beginning ati1, chooses its end, and each iteration addsnums[j1]tosum1. - Pick the second subarray. Inside the
j1loop,i2runs fromj1 + 1, so the second subarray starts after the first one ends.sum2and thej2loop work exactly likesum1andj1. - Pick the third subarray. Inside the
j2loop,i3runs fromj2 + 1, withsum3andj3built the same way. - Compare the total. In the innermost loop,
sum1 + sum2 + sum3is the total of one valid triple, andMath.Maxkeeps the best one seen. - Return after all the loops. Once the outermost loop finishes, every valid triple has been tried, and
maxSumholds the answer.
The solution in C#
class Solution {
public int MaxSumOfThreeSubarrays(int[] nums) {
int n = nums.Length;
int maxSum = int.MinValue;
for (int i1 = 0; i1 < n; ++i1 ) {
int sum1 = 0;
for (int j1 = i1; j1 < n; ++j1) {
sum1 += nums[j1];
for (int i2 = j1 + 1; i2 < n; ++i2) {
int sum2 = 0;
for (int j2 = i2; j2 < n; ++j2) {
sum2 += nums[j2];
for (int i3 = j2 + 1; i3 < n; ++i3) {
int sum3 = 0;
for (int j3 = i3; j3 < n; ++j3) {
sum3 += nums[j3];
maxSum = Math.Max(maxSum, sum1 + sum2 + sum3);
}
}
}
}
}
}
return maxSum;
}
}
C# details worth noticing
int.MinValueis the smallestint, -2,147,483,648. It is safe as a starting value because the first comparison always replaces it. Never add anything to it, though: arithmetic onintwraps around silently in C# unless you opt in to checking, soint.MinValue - 1becomes the largestint.- Variables declared inside a loop are created fresh on every iteration. That is what resets
sum1,sum2andsum3without any extra code. ++iandi++behave the same in aforupdate clause, because the value of the expression isn't used.Math.Maxis capitalised, as are all C# method names.math.maxdoesn't compile.
Complexity
Each of the six indices ranges over up to n positions, and they are ordered, so the loops visit about n⁶ / 720 combinations. That is O(n⁶) time. For 10 elements it is trivial, but for 100 elements it is already around a trillion steps divided by 720, still more than a billion. Space is O(1): a handful of int variables.
The lessons that follow bring this down by noticing that, for a fixed middle subarray, the best first and third subarrays can be found independently.
Edge cases and common mistakes
- All negative numbers. For
[-1, -2, -3, -4]the answer is-6, from the subarrays[-1],[-2]and[-3]. A starting value of 0 would wrongly return 0. - Exactly three numbers. Each element becomes its own subarray and the answer is their total. The loops handle this without special code.
- Overlapping subarrays. Starting
i2atj1instead ofj1 + 1lets two subarrays share an element, so it would be counted twice. - Forgetting to reset a sum. If
sum2were declared outside thei2loop, it would carry elements from the previous start. - Empty subarrays. Starting an end index below its start index would allow an empty subarray, which the problem forbids.
Testing
Inputs worth trying, with results from running this code:
[2, 3, -8, 7, -2, 9, -9, 7, -2, 4]returns28.[-1, -2, -3, -4]returns-6.[5, -1, 5]returns9.