LESSON 220 OF 348 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Kotlin: Trying Every Middle Subarray

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 11

Guided

Ctrl + Enter to check

KOTLIN · PARTIAL SUMS #2

Max Sum Of Three Subarrays in Kotlin, explained

Problem overview

The function maxSumOfThreeSubarrays receives an IntArray named nums with at least three numbers. It must pick 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, and the numbers can be negative.

In the example [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 other choice does better.

Approach: fix the middle subarray

Choosing three subarrays at once is a lot of freedom. Fixing the middle one removes most of it. Once the middle subarray covers indices i to j, the first subarray must lie somewhere inside nums[0..i - 1] and the third somewhere inside nums[j + 1..n - 1]. The two outer choices are independent, so each should simply be the best subarray in its region.

That turns the problem into a smaller one that you may already know: the maximum sum of a single non-empty subarray, solved in one pass by Kadane's algorithm. The plan is:

try every middle subarray nums[i..j];
add the best subarray on its left, the middle sum, and the best subarray on its right;
keep the largest total.

This lesson calls Kadane's algorithm again for every left and right region, which is easy to write but slow: about n² middle subarrays, each costing O(n). The next lessons in this chapter store the left and right answers in arrays to remove that repeated work. Here the focus is on getting the structure right.

Step by step

Store the size in n with val, since it never changes.
Start the answer at Int.MIN_VALUE, declared with var. Starting at 0 would be wrong: if every number is negative, the true answer is negative, and 0 would beat it.
Loop over the first index i of the middle subarray from 1 to n - 1. It starts at 1 because the first subarray needs at least one element before it.
Compute sum1, the best subarray sum of nums[0..i - 1], by calling maxSumSubarray on a copy of that slice.
Reset sum2 to 0 for every i. It will hold the sum of the middle subarray, which starts empty.
Loop over the last index j of the middle subarray, from i to n - 2, so at least one element is left for the third subarray.
Extend the middle subarray by adding nums[j] to sum2. Because j grows by one each time, this keeps sum2 equal to the sum of nums[i..j] without re-adding the whole range.
Compute sum3, the best subarray sum of nums[j + 1..n - 1].
Update the answer with sum1 + sum2 + sum3 if it is larger.
Return the answer after the outer loop.
Write the helper maxSumSubarray, Kadane's algorithm: maxSum is the best sum of a subarray ending at the current element, and result is the best seen overall.

The solution in Kotlin

class Solution {
    fun maxSumSubarray(nums: IntArray): Int {
        var result = nums[0]
        var maxSum = 0
        for (value in nums) {
            maxSum = value + maxOf(maxSum, 0)
            result = maxOf(result, maxSum)
        }
        return result
    }

    fun maxSumOfThreeSubarrays(nums: IntArray): Int {
        val n = nums.size
        var maxSum = Int.MIN_VALUE
        for (i in 1 until n) {
            val sum1 = maxSumSubarray(nums.copyOfRange(0, i))
            var sum2 = 0
            for (j in i until n - 1) {
                sum2 += nums[j]
                val sum3 = maxSumSubarray(nums.copyOfRange(j + 1, n))
                maxSum = maxOf(maxSum, sum1 + sum2 + sum3)
            }
        }
        return maxSum
    }
}

Kotlin details worth a closer look:

The end of copyOfRange is excluded. nums.copyOfRange(0, i) holds indices 0 to i - 1, and nums.copyOfRange(j + 1, n) holds indices j + 1 to n - 1. It returns a new IntArray, so the original is untouched.
until excludes its upper bound. for (j in i until n - 1) runs j from i to n - 2. When i is n - 1 the range is empty and the body never runs, so no copy of an empty slice is made.
The loop variable is called value. val is a keyword in Kotlin and can't be a name.
Kadane's step. value + maxOf(maxSum, 0) extends the previous run when its sum is positive and starts fresh otherwise. Starting result at nums[0], not 0, keeps all-negative arrays correct. Since maxSum starts at 0, the first element simply becomes nums[0].
maxOf is a plain function. It takes two values and returns the larger one, with no import needed.
Int is 32 bits. A total beyond about 2.1 billion would wrap around silently. The lesson's inputs stay far from that, but with huge values you would switch to Long.

Complexity

Time: O(n³). The two loops try about n²/2 middle subarrays. For each one, maxSumSubarray and copyOfRange each work through up to n elements. The loops multiplied by the linear work give cubic time.

Space: O(n). Each copyOfRange allocates a new array of up to n elements. The garbage collector can reclaim it afterwards, so only a few copies exist at a time.

Edge cases and common mistakes

All negative numbers. For [-1, -2, -3] the only choice is three single elements, so the answer is -6. An answer initialised at 0 would return 0.
Exactly three numbers. The array [1, 2, 3] gives 6: i is 1, j is 1, and each side has exactly one element.
Letting the middle reach the end. If j could be n - 1, the copy nums.copyOfRange(n, n) would be empty, and maxSumSubarray would then crash reading nums[0] of an empty array.
Starting i at 0. That leaves nothing for the first subarray, with the same crash on an empty slice.
Forgetting to reset sum2. Declaring it outside the outer loop would carry the previous middle subarray's sum into the next one.
Off-by-one in the slices. Because the end of copyOfRange is excluded, passing i - 1 or j in its place would drop one element.

Testing

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

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

Start learning free