LESSON 211 OF 348 · PARTIAL SUMS #1

Max Sum of Three Subarrays in Kotlin: Brute Force Over Six Indices

Practice O(n⁶) Read the full explanation

Given an array nums of integers, find three non-overlapping subarrays with maximum sum.

Return the total sum of the three subarrays

Example:

Input: [2, 3, -8, 7, -2, 9, -9, 7, -2, 4]
Output: 28
Explanation: Subarrays [2, 3], [7, -2, 9] and [7, -2, 4]
             have the maximum sum of 28

Note:

Subarrays must be non-empty
nums contains at least three numbers

STEP 1 OF 16

Guided

Ctrl + Enter to check

KOTLIN · PARTIAL SUMS #1

Max Sum Of Three Subarrays in Kotlin, explained

Problem overview

The function maxSumOfThreeSubarrays receives an IntArray called nums with at least three numbers. It must choose three non-overlapping, non-empty, contiguous subarrays so that their combined sum is as large as possible, and return that sum. The subarrays can be any length, and they can sit right next to each other.

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] add up to 5 + 14 + 9 = 28, and no choice of three does better. The two negative numbers, -8 and -9, that separate the groups are left out.

Approach: try every triple of subarrays

A subarray is fixed by its first and last index. Three non-overlapping subarrays, in left-to-right order, are fixed by six indices:

i1 <= j1 < i2 <= j2 < i3 <= j3

The brute force walks through every such sextuple, adds up the three sums and keeps the largest. It is the most direct reading of the problem, and it is a good first solution because each line follows from the statement. It is also very slow, and the later lessons on this problem replace it with faster ideas.

Two ideas keep the code short:

Build each sum while extending the subarray. When j1 moves one step right, the first subarray gains one element, so sum1 grows by nums[j1]. There is no need to add the whole subarray again.
Nest the loops in left-to-right order. The start of each subarray begins after the end of the previous one, which guarantees there is no overlap and avoids counting the same triple in a different order.

Step by step

Store nums.size in n with val, because it is used in every loop bound and never changes.
Declare maxSum with var, starting at Int.MIN_VALUE. Every subarray must be non-empty, so the answer can be negative, and a starting value of 0 could beat it. The smallest possible Int loses to any real sum.
Loop i1 over every index for the start of the first subarray.
Declare sum1 inside that loop, starting at 0 for an empty subarray. Each new start gets a fresh sum.
Loop j1 from i1 to the end. It is the last index of the first subarray, and it can equal i1 for a one-element subarray.
Add nums[j1] to sum1 at the top of that loop, so sum1 covers [i1, j1].
Loop i2 from j1 + 1 to the end. The second subarray starts after the first one ends.
Declare sum2 inside the i2 loop, starting at 0.
Loop j2 from i2 to the end, the last index of the second subarray.
Add nums[j2] to sum2.
Loop i3 from j2 + 1 to the end, the start of the third subarray.
Declare sum3 inside the i3 loop, starting at 0.
Loop j3 from i3 to the end, the last index of the third subarray.
Add nums[j3] to sum3.
Update maxSum with maxOf(maxSum, sum1 + sum2 + sum3). At this point all three subarrays are fully chosen.
Return maxSum after the outermost loop finishes.

The solution in Kotlin

class Solution {
    fun maxSumOfThreeSubarrays(nums: IntArray): Int {
        val n = nums.size
        var maxSum = Int.MIN_VALUE
        for (i1 in 0 until n) {
            var sum1 = 0
            for (j1 in i1 until n) {
                sum1 += nums[j1]
                for (i2 in (j1 + 1) until n) {
                    var sum2 = 0
                    for (j2 in i2 until n) {
                        sum2 += nums[j2]
                        for (i3 in (j2 + 1) until n) {
                            var sum3 = 0
                            for (j3 in i3 until n) {
                                sum3 += nums[j3]
                                maxSum = maxOf(maxSum, sum1 + sum2 + sum3)
                            }
                        }
                    }
                }
            }
        }
        return maxSum
    }
}

The Kotlin details worth a closer look:

until excludes its upper bound. i1 until n visits 0 to n - 1, which are exactly the valid indices. The inclusive form would be 0..n - 1.
Empty ranges are fine. When j1 + 1 is already n, (j1 + 1) until n is empty and the loop body simply doesn't run. This is why no explicit bounds checks appear in the code.
Loop variables are vals. The indices are read-only inside the body. The running sums, which change, are declared with var.
Where each sum is declared decides when it resets. sum2 lives inside the i2 loop, so every new start for the second subarray begins from 0, while it keeps growing as j2 moves. The same holds for sum1 and sum3.
Int.MIN_VALUE as a sentinel. It is -2147483648. If no triple exists, which happens when nums has fewer than three elements, the function returns this value. With three or more numbers, at least one triple is always found.

Complexity

Time: O(n⁶). Each of the six indices ranges over up to n positions, and the constraint i1 <= j1 < i2 <= j2 < i3 <= j3 only cuts the count by a constant factor. The work per innermost step is constant. Doubling the length of the array multiplies the running time by roughly 64, so this version only suits small inputs.

Space: O(1). The function keeps a handful of integers.

Edge cases and common mistakes

All negative numbers. [-1, -2, -3] returns -6: three non-empty subarrays are required, so all three elements are used. Initializing maxSum with 0 would wrongly return 0.
Exactly three numbers. The only option is one element per subarray, so the answer is the sum of the whole array.
Adjacent subarrays. [5, 5, 5] returns 15. Starting i2 at j1 + 1 allows the second subarray to begin right after the first, with no gap.
Skipping elements. [1, -5, 2, -5, 3] returns 6, from [1], [2] and [3]. The numbers between the chosen subarrays don't have to be used.
Allowing overlap. Starting i2 at j1 instead of j1 + 1 would let two subarrays share an element and count it twice.
Declaring a sum in the wrong place. If sum2 were declared outside the i2 loop, it would carry over from the previous start and produce sums of subarrays that don't exist.
Too few elements. With fewer than three numbers the function returns Int.MIN_VALUE, but the statement guarantees at least three.

Testing

[2, 3, -8, 7, -2, 9, -9, 7, -2, 4] gives 28.
[-1, -2, -3] gives -6.
[1, -5, 2, -5, 3] gives 6.
[5, 5, 5] gives 15.
[1, 2, 3, 4] gives 10.

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free