Start learning free

LESSON 210 OF 348 · PARTIAL SUMS #1

Maximum Sum Subarray in Kotlin: O(n) with Prefix Sums

Practice O(n) Read the full explanation

( Prefix Sums Approach )


Given an input array that may contain both positive and negative integers, find the sum of continuous subarray of numbers which has the largest sum.

Example:

Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7

Note:

Your algorithm should run in O(n) time and use at most O(n) extra space.


STEP 1 OF 7
    Ctrl + Enter to check

    KOTLIN · PARTIAL SUMS #1

    Maximum Sum Subarray in Kotlin, explained

    Problem overview

    The function maxSumSubarray receives an IntArray called nums that may hold positive and negative numbers. It must return the largest sum of a contiguous block of elements. The block can't be empty, and it can be as short as a single element or as long as the whole array.

    In the example, nums = [-2, -5, 6, -2, -3, 1, 5, -6] and the answer is 7, from the block [6, -2, -3, 1, 5]: 6 - 2 - 3 + 1 + 5 = 7. The statement asks for O(n) time and at most O(n) extra space. This version of the lesson, the prefix sums approach, actually needs only a few variables.

    Approach: best block ending here = running total minus the lowest earlier total

    The slow way tries every start and every end and adds up each block, which costs O(n²) at best and O(n³) if each block is summed from scratch. Prefix sums remove most of that work.

    Call the sum of the first j elements the prefix sum at j. The sum of a block that starts after position i and ends at position j is the prefix sum at j minus the prefix sum at i. So for a fixed end j, the best block ending there uses the smallest earlier prefix sum. Subtracting the smallest number leaves the largest difference.

    That gives a one-pass algorithm. Walk through the array keeping the running total (partialSum) and the smallest prefix sum seen before the current element (minSum). At each element, partialSum - minSum is the best block that ends at that element, and the answer is the maximum of these values.

    The empty prefix counts as an earlier prefix with sum 0. That is why minSum starts at 0: it allows a block that begins at index 0.

    Here is the example, element by element:

    elementpartialSumminSum before itbest block ending here
    -2-20-2
    -5-7-2-5
    6-1-76
    -2-3-74
    -3-6-71
    1-5-72
    50-77
    -6-6-71

    The largest value in the last column is 7, which matches the expected answer. The smallest prefix sum, -7, was reached after the second element, so the winning block starts right after it: [6, -2, -3, 1, 5].

    Step by step

    1. Declare partialSum and minSum as vars set to 0. Both change in the loop, and 0 stands for the empty prefix.
    2. Declare result with var, starting at nums[0]. A one-element block is a valid answer, so nums[0] is a value the result can never fall below. Starting at 0 would be wrong when every number is negative, because the answer must be a real, non-empty block.
    3. Loop over the elements with for (value in nums). The name val is a keyword in Kotlin, which is why the loop variable is called value.
    4. Add value to partialSum. It now holds the sum of everything up to and including this element.
    5. Update result with maxOf(result, partialSum - minSum), the best block ending at this element.
    6. Update minSum with minOf(minSum, partialSum), so the next element can start a block right after this one.
    7. Return result once the loop is done.

    The solution in Kotlin

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

    The Kotlin details worth a closer look:

    • var versus val. A val can be assigned once. All three accumulators are reassigned inside the loop, so they are vars.
    • maxOf and minOf. These are standard-library functions that return the larger or smaller of their arguments. They replace an if statement and keep each update on one line.
    • The order of the two updates matters. result is updated before minSum. If minSum were updated first, it could become equal to the current partialSum, and the difference would be 0, which stands for an empty block. With [-3, -1, -2] that would return 0 instead of -1.
    • Int is 32 bits. Sums beyond about 2.1 billion wrap around silently. If the inputs could be that large, partialSum and the result would need to be Long.
    • Iterating an IntArray. for (value in nums) reads the elements directly and needs no index. It also avoids the off-by-one mistakes of a manual index loop.

    Complexity

    Time: O(n). The loop runs once per element, and each iteration does a constant amount of work: one addition, one maxOf and one minOf.

    Space: O(1). The function keeps three Int variables and never builds an array of prefix sums. That is within the O(n) limit in the statement.

    Edge cases and common mistakes

    • All negative numbers. [-3, -1, -2] returns -1, the best single element. Initializing result with 0 would return 0, which is the sum of no block at all.
    • A single element. [4] returns 4.
    • An empty array. nums[0] throws an ArrayIndexOutOfBoundsException. The lesson's input always has at least one number.
    • Forgetting the empty prefix. If minSum started at nums[0] or at some large value, a block beginning at index 0 could never be chosen.
    • Swapping the two updates. As described above, this lets an empty block win when all numbers are negative.
    • Overflow. Very large values can exceed the range of Int, and the sums wrap around without an error.

    Testing

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