Start learning free

LESSON 233 OF 414 · PARTIAL SUMS #1

Maximum Sum Subarray in Scala: Prefix Sums in O(n)

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

    SCALA · PARTIAL SUMS #1

    Maximum Sum Subarray in Scala, explained

    Problem overview

    The method maxSumSubarray receives an Array[Int] called nums with positive and negative numbers and returns the largest sum of any continuous, non-empty run of elements.

    For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7, from [6, -2, -3, 1, 5].

    This version of the lesson allows O(n) time and up to O(n) extra space, and it solves the problem with prefix sums. The reference solution turns out to need only a couple of variables, but the idea behind it comes from prefix sums.

    Approach: a subarray sum is a difference of two prefix sums

    The prefix sum at position i is the sum of all elements from index 0 up to i. Take two prefix sums, one taken after element j and one taken earlier, after element i, where i < j. Their difference is the sum of the elements i + 1 through j:

    sum(i + 1 .. j) = prefix(j) - prefix(i)

    So the best run that ends at position j is prefix(j) minus the smallest earlier prefix sum. Subtracting the smallest one leaves the largest possible difference. The empty prefix, with sum 0, counts as an earlier prefix too. It is what lets a run start at index 0.

    That means a single pass is enough. Keep the running prefix sum and the smallest prefix sum seen so far. For each element, update the answer with the difference between the two, then update the minimum.

    On the example, the prefix sums are -2, -7, -1, -3, -6, -5, 0, -6. The smallest prefix sum seen before reaching the value 5 (prefix 0) is -7, and 0 - (-7) = 7. That difference corresponds to the run that starts right after the -7 prefix, which is the run [6, -2, -3, 1, 5].

    Step by step

    1. Declare partialSum and minSum as vars with value 0. The loop hasn't read anything yet, so the prefix is empty with sum 0, and the smallest prefix seen so far is that same empty prefix.
    2. Declare result as a var holding nums(0). A single element is a real subarray, so this is a value the answer can never be below. Starting at 0 would be wrong when every number is negative.
    3. Loop over the elements with for (value <- nums). The name value is used because val is a Scala keyword.
    4. Add value to partialSum, so it becomes the prefix sum that includes the current element.
    5. Update result with math.max(result, partialSum - minSum). Here minSum is still the minimum over the prefixes that come before the current element, which is what keeps the run non-empty.
    6. Update minSum with math.min(minSum, partialSum), so the current prefix can serve as the starting point for later elements.
    7. Return result. In Scala the last expression of the method is its value, so writing result on its own line is enough.

    The order of steps 5 and 6 matters. If minSum were updated first, then for a negative number minSum could equal partialSum, and the difference would be 0, which stands for an empty run.

    The solution in Scala

    class Solution {
    def maxSumSubarray(nums: Array[Int]): Int = {
        var partialSum = 0
        var minSum = 0
        var result = nums(0)
        for (value <- nums) {
            partialSum += value
            result = math.max(result, partialSum - minSum)
            minSum = math.min(minSum, partialSum)
        }
        result
    }
}

    The Scala details worth knowing:

    • Three vars. All three are reassigned inside the loop. Using val for any of them would be a compile error on reassignment.
    • += works on vars of numeric type. partialSum += value means partialSum = partialSum + value. Scala has no ++ operator, so += 1 is how you add one.
    • Array indexing uses parentheses. nums(0) is the first element.
    • No return needed. The final line, result, is the value of the method body.
    • Int overflow is silent. Int is 32 bits, so a prefix sum above about 2.1 billion would wrap around to a negative number.

    Complexity

    Time: O(n). One pass, with constant work per element.

    Space: O(1) here. A textbook prefix-sum solution would store all n prefix sums in an array, which is where the O(n) allowance comes from. This code keeps only the running sum and the minimum, because each prefix is used the moment it is computed.

    Edge cases and common mistakes

    • All numbers negative. For [-4, -1, -7] the answer is -1. At the second element the prefix sum is -5 and minSum is -4, so the difference is -1. Because minSum still holds the earlier prefixes, the difference is never an empty run.
    • The empty prefix. Starting minSum at 0 is what allows a run to begin at index 0. With [3, 4] the answer 7 is partialSum - 0.
    • Initializing result with 0. That would return 0 for an all-negative array, but no non-empty subarray has that sum.
    • Updating minSum before result. The difference would then be allowed to use the current prefix as its own starting point, giving an empty run with sum 0.
    • An empty array. nums(0) throws an ArrayIndexOutOfBoundsException. The method assumes at least one element.

    Testing

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