Start learning free

LESSON 231 OF 414 · FREE CODING INTERVIEW QUESTIONS

Maximum Sum Subarray in Scala: O(n^2) Brute Force with Running Sums

Practice O(n2) Read the full explanation

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^2) time and use O(1) extra space.




Let's come up with a brute force approach. Brute force tries each and every candidate to our solution. For this problem, the candidates are all the subarrays of nums. How can we try out each subarray?

A subarray is defined by its left endpoint, let's name it index i and its right point, let's name it index j. We should go through each pair of indices (i, j) such that 0 <= i <= j < n, where n is the length of nums. How can we achieve this?

Using two nested for loops! The first loop will try out each possible i between 0 and n - 1. The second loop will be written inside the first one and will try out each possible j between i and n - 1. 
for each i : 0 to n - 1:
		for each j : i to n - 1:
We will use a variable maxSum to store the greatest sum found so far and for each pair (i, j), update maxSum with sum(nums[i...j]) if it's the case: 
maxSum = nums[0]
for each i : 0 to n - 1:
	for each j : i to n - 1:
		maxSum = max(maxSum, sum(nums[i...j]))
return maxSum
All we have to do now is find a way of getting sum(nums[i...j]) in O(1) time. How can we do this?

One way is using Partial Sums. But that implies using an extra array, which takes O(n) extra space. There is a better way. We can use a variable sum to store the sum of the current subarray sum(nums[i...j]). 
maxSum = nums[0]
for each i : 0 to n - 1:
	for each j : i to n - 1:
		maxSum = max(maxSum, sum)
return maxSum
How should we update this variable throught the algorithm to make sure that it always stores the correct sum?

Each time we increment j in the second loop, we should add nums[j] to sum. Also, each time we increment i in the first loop, we start with a new empty subarray so we should reset sum to 0: 
maxSum = nums[0]
for each i : 0 to n - 1:
	sum = 0
	for each j : i to n - 1:
		sum += nums[j]
		maxSum = max(maxSum, sum)
return maxSum

STEP 1 OF 7
    Ctrl + Enter to check

    SCALA · FREE CODING INTERVIEW QUESTIONS

    Maximum Sum Subarray in Scala, explained

    Problem overview

    The method maxSumSubarray receives an Array[Int] called nums, which may hold positive and negative numbers. It returns the largest sum that any subarray of nums can have. A subarray is a run of neighbouring elements, from some index i to some index j with i <= j.

    For nums = Array(-2, -5, 6, -2, -3, 1, 5, -6) the answer is 7, from the subarray 6, -2, -3, 1, 5. The statement allows O(n^2) time and O(1) extra space.

    Approach: try every subarray, but sum smartly

    The brute-force idea is to try every candidate. A subarray is fixed by its first index i and its last index j, so two nested loops can visit every pair. For each pair, compare the subarray's sum with the best sum found so far.

    Computing each sum from scratch with a third loop would make the whole thing O(n^3). The trick that brings it down to O(n^2) is to notice that, for a fixed i, each step of j just adds one element to the subarray. So keep a running sum: reset it to 0 when i changes, and add nums(j) each time j moves. No extra array of prefix sums is needed, which keeps the extra space constant.

    Faster approaches exist, and this course revisits the problem with them. This lesson sticks to the quadratic one.

    Tracing one start index

    In the example, take i = 2, where nums(2) is 6. As j goes from 2 to 7 the running sum takes the values 6, 4, 1, 2, 7 and 1. The largest of those is 7, reached at j = 6. No other start index does better, so 7 is the answer.

    Step by step

    1. Declare maxSum with var and initialize it to nums(0). Don't start at 0: if every number is negative, the best subarray has a negative sum, and 0 would be larger than any real answer. A single element is itself a subarray, so nums(0) is a sum that really exists. Use var because it changes.
    2. Loop over each start index with for (i <- nums.indices). nums.indices is the range from 0 to nums.length - 1.
    3. Declare var sum = 0 inside that loop. It belongs to one start index, so it is created fresh each time and is not visible outside the loop. Starting from 0 means an empty subarray, which is what we have before adding any element.
    4. Loop over each end index with for (j <- i until nums.length). The end can't be before the start, and until excludes its upper bound, so j covers i through nums.length - 1.
    5. Add the new element: sum += nums(j), inside the inner loop.
    6. Update the best: maxSum = math.max(maxSum, sum), which keeps the larger of the two in one line.
    7. Finish with maxSum on its own line. It is the last expression of the method, so it is the returned value.

    The solution in Scala

    class Solution {
    def maxSumSubarray(nums: Array[Int]): Int = {
        var maxSum = nums(0)
        for (i <- nums.indices) {
            var sum = 0
            for (j <- i until nums.length) {
                sum += nums(j)
                maxSum = math.max(maxSum, sum)
            }
        }
        maxSum
    }
}

    The Scala details worth a closer look:

    • Ranges. nums.indices and i until nums.length are both ranges of Int. 0 until 3 contains 0, 1 and 2; 1 to 3 would contain 1, 2 and 3. When i equals nums.length, i until nums.length is empty, so the inner loop simply doesn't run.
    • The last expression is the result. There is no return. If a line after the loops were missing, the method would end with the loop itself, whose value is Unit, and the compiler would reject it because the method promises an Int.
    • math.max. It is available without an import and works on Int values, returning an Int.
    • Array indexing. nums(j) uses parentheses. An index outside the array throws an ArrayIndexOutOfBoundsException.
    • Int overflow. The sum is a 32-bit Int, and overflow wraps silently instead of raising an error. For Array(Int.MaxValue, 1) the running sum wraps to a negative number, so the method returns 2147483647 rather than the true sum of 2147483648. The lesson's inputs are small enough that this doesn't matter, but use Long if sums can grow that large.

    Complexity

    Time: O(n^2). For n elements, the inner loop runs n times for i = 0, n - 1 times for i = 1, and so on down to once. That adds up to n(n + 1) / 2 iterations, each of which does constant work.

    Space: O(1). The method uses maxSum, sum and the two loop indexes, whatever the size of nums. The ranges are not stored as lists; they produce their values one at a time.

    Edge cases and common mistakes

    • All negative numbers. Array(-3, -1, -2) returns -1: the best subarray is the single element -1. Initializing maxSum to 0 would return 0, a sum no subarray has.
    • One element. Array(4) returns 4.
    • All positive numbers. Array(1, 2, 3) returns 6, the whole array.
    • A negative gap worth crossing. Array(5, -10, 5) returns 5. Crossing the -10 would cost more than the second 5 gives back.
    • Forgetting to reset sum. If sum is declared outside the outer loop, each start index inherits the previous total and the results are wrong.
    • Starting j at 0. The inner loop must start at i. Otherwise it adds elements that are not part of the subarray beginning at i.
    • Empty array. nums(0) would throw, so the method expects at least one element.

    Testing

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