Start learning free

LESSON 222 OF 348 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Kotlin: O(n) with a Running Best Difference

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 21
    Ctrl + Enter to check

    KOTLIN · PARTIAL SUMS #2

    Max Sum Of Three Subarrays in Kotlin, explained

    Problem overview

    The function maxSumOfThreeSubarrays takes an IntArray named nums with at least three numbers and returns the largest total of three non-empty, non-overlapping subarrays. The numbers may be negative.

    For [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] the best subarrays are [2, 3], [7, -2, 9] and [7, -2, 4], and the answer is 5 + 14 + 9 = 28.

    Approach: remove the loop over the middle subarray's start

    The previous idea precomputes leftMaxSum and rightMaxSum, then tries every middle subarray with two nested loops, which is O(n²). The goal here is a single loop.

    Fix the middle subarray's last index i and let it start at some index k, where 1 <= k <= i. Its sum is a difference of prefix sums. Let P(x) be the sum of nums[0..x - 1], so P(0) is 0. Then the middle subarray nums[k..i] sums to P(i + 1) - P(k), and the total for this choice is:

    leftMaxSum[k - 1] + (P(i + 1) - P(k)) + rightMaxSum[i + 1]

    Only the part leftMaxSum[k - 1] - P(k) depends on k. For a fixed i, the best k is the one that makes it largest. As i moves right, one more start becomes available and no earlier one disappears, so a running maximum over k is enough. That running maximum is maxDiff, and it replaces the inner loop.

    To see why this is correct, imagine the middle subarray ends at i and you consider two possible starts, k1 and k2. Both share the same P(i + 1) and the same third subarray, so the comparison between them is just leftMaxSum[k - 1] - P(k). A start that loses now also loses for every later i, because the shared terms change equally for both. So only the largest value ever seen matters, and one variable is enough to hold it.

    The approaches to this problem form a ladder. Calling Kadane's algorithm again for every split costs O(n³). Storing the left and right answers costs O(n²). This lesson adds prefix sums and a running maximum and reaches O(n).

    Step by step

    1. Store the size in n.
    2. Build leftMaxSum with a Kadane pass: maxSum holds the best run ending at the current index, and leftMaxSum[i] is the larger of leftMaxSum[i - 1] and that run.
    3. Build rightMaxSum with the mirror pass from the end, counting down with downTo.
    4. Reset maxSum to Int.MIN_VALUE for the answer. It must start below every possible total.
    5. Create partialSum starting at nums[0]. At the top of each iteration it equals the sum of nums[0..i - 1], which is P(i).
    6. Create maxDiff at Int.MIN_VALUE. It tracks the largest leftMaxSum[k - 1] - P(k) over the starts seen so far.
    7. Loop i from 1 to n - 2. The middle subarray needs a first subarray before it and a third one after it.
    8. Add the new start. Update maxDiff with leftMaxSum[i - 1] - partialSum, which is the option of starting the middle subarray exactly at i.
    9. Advance partialSum by nums[i] so it becomes P(i + 1).
    10. Update the answer with partialSum + rightMaxSum[i + 1] + maxDiff: the prefix sum, the best third subarray, and the best combination of first subarray and start of the middle one.
    11. Return the answer.

    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
        var partialSum = nums[0]
        var maxDiff = Int.MIN_VALUE
        for (i in 1 until n - 1) {
            maxDiff = maxOf(leftMaxSum[i - 1] - partialSum, maxDiff)
            partialSum += nums[i]
            maxSum = maxOf(partialSum + rightMaxSum[i + 1] + maxDiff, maxSum)
        }

        return maxSum
    }
}

    Tracing the example

    At i = 5, before the update, partialSum is 2 + 3 - 8 + 7 - 2 = 2. The starts seen so far gave maxDiff values such as leftMaxSum[2] - P(3) = 5 - (-3) = 8 (start at index 3). After the update at i = 5, the candidate leftMaxSum[4] - P(5) = 7 - 2 = 5 is smaller, so maxDiff stays 8. Then partialSum becomes 11, and the total is 11 + rightMaxSum[6] + 8 = 11 + 9 + 8 = 28. That is the answer, with the middle subarray starting at index 3.

    Kotlin details worth knowing:

    • Why Int.MIN_VALUE is safe for maxDiff. It is replaced on the first iteration, because maxOf keeps the larger value. It is never added to anything while it still holds the minimum, so there is no overflow.
    • A var reused for two results. maxSum serves the right pass and then the answer. The earlier values live on in rightMaxSum.
    • The loop bound. 1 until n - 1 stops at n - 2, so rightMaxSum[i + 1] is always inside the array.
    • Arrays created with IntArray(n) start as zeros and are overwritten before use.
    • Int overflow wraps silently. The sums stay small in the lesson, but huge values would need Long.

    Complexity

    Time: O(n). There are three passes over the array, each doing constant work per element.

    Space: O(n). The two arrays leftMaxSum and rightMaxSum take n integers each. The rest is a handful of variables.

    Edge cases and common mistakes

    • All negative numbers. [-1, -2, -3] returns -6, which is why the answer starts at Int.MIN_VALUE and not 0.
    • Exactly three numbers. The loop runs once, with i = 1, and [1, 2, 3] gives 6.
    • Updating in the wrong order. maxDiff must use partialSum before nums[i] is added, since it needs the sum of nums[0..i - 1]. Swapping the two lines would subtract the wrong prefix.
    • Using leftMaxSum[i] in place of leftMaxSum[i - 1]. The first subarray must finish before the middle one starts, so it can't include index i.
    • Starting partialSum at 0. The loop starts at i = 1, so by then nums[0] is already part of the prefix.

    Testing

    • [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] gives 28.
    • [1, 2, 3] gives 6.
    • [1, 2, 3, 4, 5] gives 15.
    • [-1, -2, -3, -4] gives -6.
    • [5, -100, 5, -100, 5] gives 15.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free