Start learning free

LESSON 221 OF 348 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Kotlin: Prefix and Suffix Best Arrays

Practice O(n2) 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 22
    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 choose three non-empty, non-overlapping subarrays and return the largest possible sum of all their elements. Numbers can be negative.

    For [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] the best choice is [2, 3], [7, -2, 9] and [7, -2, 4], which sum to 5 + 14 + 9 = 28.

    Approach: precompute the best left and right subarray

    Fix the middle subarray as nums[i..j]. The first subarray is the best one anywhere in nums[0..i - 1] and the third is the best one anywhere in nums[j + 1..n - 1]. A direct solution recomputes those two values for every pair (i, j) with Kadane's algorithm, which makes it cubic.

    The same left value is needed for every j that goes with a given i, and the same right value is needed for many different i. So compute them once:

    • leftMaxSum[i] is the best subarray sum inside the prefix nums[0..i];
    • rightMaxSum[i] is the best subarray sum inside the suffix nums[i..n - 1].

    Each array costs one linear pass. After that, a middle subarray costs a constant amount of work, and trying all of them is O(n²).

    The two arrays on the example

    For [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] the passes produce:

    leftMaxSum  = [2, 5, 5, 7, 7, 14, 14, 14, 14, 14]
rightMaxSum = [14, 14, 14, 14, 9, 9, 9, 9, 4, 4]

    Take the middle subarray [7, -2, 9], at indices 3 to 5. The best first subarray is leftMaxSum[2], which is 5 (from [2, 3]). The best third subarray is rightMaxSum[6], which is 9 (from [7, -2, 4]). The total is 5 + 14 + 9 = 28, and no other middle subarray beats it. Each array is a running maximum: leftMaxSum never decreases from left to right, and rightMaxSum never increases.

    Step by step

    1. Store the size as n.
    2. Create leftMaxSum with IntArray(n), and set element 0 to nums[0]: the only subarray of a one-element prefix is that element.
    3. Keep maxSum, the best sum of a subarray that ends at the current index, starting at nums[0].
    4. Walk i from 1 to n - 1. First update maxSum to nums[i] + maxOf(maxSum, 0): the best run ending at i either extends the previous run, if its sum is positive, or starts at i.
    5. Fill leftMaxSum[i] with the larger of leftMaxSum[i - 1] and maxSum. The best subarray in the prefix either lies entirely before i or ends at i.
    6. Build rightMaxSum the same way from the other end. Set its last element to nums[n - 1], reuse maxSum (now the best run starting at the current index) and walk i from n - 2 down to 0.
    7. Reset maxSum to Int.MIN_VALUE to hold the final answer. It must start below any possible total, because the answer can be negative.
    8. Loop over the middle subarray's first index i from 1 to n - 1, and read sum1 from leftMaxSum[i - 1].
    9. Loop over its last index j from i to n - 2. Add nums[j] to sum2, which was reset to 0 for this i, and read sum3 from rightMaxSum[j + 1].
    10. Keep the largest sum1 + sum2 + sum3 and return it after the loops.

    The solution in Kotlin

    class Solution {

    fun maxSumOfThreeSubarrays(nums: IntArray): Int {
        val n = nums.size

        val leftMaxSum = IntArray(n)
        leftMaxSum[0] = nums[0]
        var maxSum = nums[0]
        for (i in 1 until n) {
            maxSum = nums[i] + maxOf(maxSum, 0)
            leftMaxSum[i] = maxOf(leftMaxSum[i - 1], maxSum)
        }

        val rightMaxSum = IntArray(n)
        rightMaxSum[n - 1] = nums[n - 1]
        maxSum = nums[n - 1]
        for (i in n - 2 downTo 0) {
            maxSum = nums[i] + maxOf(maxSum, 0)
            rightMaxSum[i] = maxOf(rightMaxSum[i + 1], maxSum)
        }

        maxSum = Int.MIN_VALUE
        for (i in 1 until n) {
            val sum1 = leftMaxSum[i - 1]
            var sum2 = 0
            for (j in i until n - 1) {
                sum2 += nums[j]
                val sum3 = rightMaxSum[j + 1]
                maxSum = maxOf(maxSum, sum1 + sum2 + sum3)
            }
        }

        return maxSum
    }
}

    Kotlin details worth knowing:

    • IntArray(n) starts filled with zeros. Every slot is overwritten here anyway, element 0 directly and the rest in the loop.
    • val on an array still allows changing its elements. val leftMaxSum means the variable can't point to another array. leftMaxSum[i] = ... changes the contents and is allowed.
    • One var, two jobs. maxSum is declared once and reassigned for the right pass and for the final answer. That works because the earlier values are no longer needed once they are stored in the arrays.
    • n - 2 downTo 0 counts down and includes both ends. A plain 0 until n - 1 would count up. If you write n - 2..0 by mistake, the range is empty because .. only counts up, and the right array would stay mostly zeros.
    • Ranges that can be empty are fine. When i is n - 1, i until n - 1 holds nothing and the inner loop is skipped.
    • Int wraps on overflow. Sums past about 2.1 billion wrap silently; use Long for such data.

    Complexity

    Time: O(n²). The two precomputing passes are O(n). The double loop tries about n²/2 middle subarrays at O(1) each, so it dominates.

    Space: O(n). The two arrays hold n integers each. This beats the previous approach, where each slice was copied again for every middle subarray.

    Edge cases and common mistakes

    • All negative numbers. For [-1, -2, -3] the answer is -6. Initialising the answer to 0 would return 0.
    • Exactly three numbers. [1, 2, 3] gives 6, with one element in each part.
    • Prefix means "inside", not "ending at". leftMaxSum[i] is a running maximum, so it never decreases as i grows. Storing only the best run ending at i would miss a better subarray that ended earlier.
    • Index shifts. The first subarray must end before the middle one starts, so use leftMaxSum[i - 1], not leftMaxSum[i]. For the third, use rightMaxSum[j + 1].
    • Letting j reach n - 1. Then rightMaxSum[j + 1] reads past the end and throws an ArrayIndexOutOfBoundsException.
    • Not resetting sum2 for each i, which would mix sums from different middle subarrays.

    Testing

    • [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] gives 28.
    • [1, 2, 3, 4, 5] gives 15, using the whole array split into three parts.
    • [-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