Start learning free

LESSON 207 OF 338 · FREE CODING INTERVIEW QUESTIONS

Maximum Sum Subarray in Go: O(n²) Time, O(1) Space

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. 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 -> n - 1:
		for each j : i -> 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 -> n - 1:
	for each j : i -> 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 gives extra space of O(n). 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 -> n - 1:
	for each j : i -> 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 -> n - 1:
	sum = 0
	for each j : i -> n - 1:
		sum += nums[j]
		maxSum = max(maxSum, sum)
return maxSum

STEP 1 OF 7
    Ctrl + Enter to check

    GO · FREE CODING INTERVIEW QUESTIONS

    Maximum Sum Subarray in Go, explained

    Problem overview

    The function maxSumSubarray receives a slice of integers, nums, that may contain both positive and negative values. It returns the largest sum that any continuous run of elements, a subarray, can have.

    For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7, from the run [6, -2, -3, 1, 5]: 6 - 2 - 3 + 1 + 5 = 7. The statement sets a budget of O(n²) time and O(1) extra space, which is the budget of a brute-force search done carefully.

    Approach

    A subarray is fully described by its first index i and its last index j, with i <= j. So the brute force is to try every such pair and keep the best sum. There are about n²/2 pairs.

    The expensive part would be adding up the elements for each pair, which costs up to O(n) and gives O(n³) in total. The way around it: for a fixed i, the subarray for j + 1 is the subarray for j with one more element on the right. So the sum doesn't need recomputing. Keep a running sum, reset it to 0 each time i moves, and add nums[j] as j advances. Every pair then costs O(1), and the whole search is O(n²) without an extra array of partial sums.

    Other lessons on this problem take the time down further. This one stays with the quadratic search.

    Step by step

    1. Declare maxSum as nums[0]. The best sum can be negative (if every element is negative), so starting at 0 would wrongly report an empty subarray. nums[0] is itself a subarray, so it is a safe starting point.
    2. Loop over the first index i from 0 to len(nums) - 1.
    3. Declare sum := 0 inside that loop. Each new i starts from an empty subarray, and the variable isn't needed outside the loop.
    4. Loop over the last index j from i to len(nums) - 1. Starting at i allows one-element subarrays.
    5. Add nums[j] to sum. Now sum equals the sum of nums[i..j].
    6. Update maxSum in one line with max: it keeps the larger of the old best and the new sum.
    7. Return maxSum after both loops have finished.

    The solution in Go

    func maxSumSubarray(nums []int) int {
    maxSum := nums[0]
    for i := 0; i < len(nums); i++ {
        sum := 0
        for j := i; j < len(nums); j++ {
            sum += nums[j]
            maxSum = max(maxSum, sum)
        }
    }
    return maxSum
}

    The Go details worth a closer look:

    • Built-in max. Since Go 1.21, max and min are built-in functions that take two or more values of the same ordered type. No import is needed. In older Go versions you would write the if yourself.
    • Scope of sum. A variable declared with := inside the outer loop's body exists only for that iteration, so it starts at 0 again every time. sum is not a Go keyword or built-in, so it is a fine variable name.
    • for is the only loop. The classic three-part form for init; condition; post { } does the job of C's for, and Go has no parentheses around the three parts.
    • Integer size. int is 64 bits on a 64-bit machine, so the running sums of ordinary test data don't overflow. If they did, Go would wrap silently instead of reporting an error.

    Complexity

    Time: O(n²). For each of the n values of i, the inner loop runs n - i times, which adds up to n(n + 1)/2 iterations, each doing constant work. Space: O(1). The function keeps three integers and two loop counters, whatever the size of nums.

    Edge cases and common mistakes

    • All negative numbers. [-3, -1, -2] gives -1, the best single element. Initialising maxSum to 0 would return 0, a sum that no subarray has.
    • A single element. [4] gives 4. The loops run once and maxSum is unchanged.
    • All positive numbers. [1, 2, 3] gives 6, the whole slice.
    • Not resetting sum. If sum were declared outside the outer loop, sums from earlier starting points would carry over and the results would describe subarrays that don't exist.
    • Starting j at 0. The inner loop must start at i, otherwise it adds elements to the left of the subarray's start.
    • Checking only the final sum. The best subarray can end before the end of the slice, so maxSum has to be updated for every j. In [5, -10, 5] the best sum is 5, not the total of 0.
    • An empty slice. nums[0] would panic with "index out of range". The lesson's inputs are never empty.

    Testing

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