Start learning free

LESSON 207 OF 347 · FREE CODING INTERVIEW QUESTIONS

Maximum Sum Subarray in C#: O(n²) Brute Force with a Running Sum

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

    C# · FREE CODING INTERVIEW QUESTIONS

    Maximum Sum Subarray in C#, explained

    Problem overview

    The method MaxSumSubarray receives an int[] named nums that may contain positive and negative numbers. 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 best subarray is [6, -2, -3, 1, 5], with sum 7. No other run does better. The statement allows O(n²) time and O(1) extra space.

    Approach: try every subarray

    A subarray is fixed by its first index i and its last index j, with i <= j. A brute force simply tries every such pair and keeps the best sum.

    Summing each subarray from scratch would add a third loop and cost O(n³). The trick is to notice that for a fixed i, moving j one step to the right only adds one element. So keep a running sum: reset it to 0 when i changes, and add nums[j] each time j moves. The sum is then always the sum of nums[i..j], and getting it costs O(1).

    A prefix-sum array would also give each subarray sum in constant time, but it needs O(n) extra space. The running sum doesn't.

    For i = 2 in the example, j runs from 2 to 7 and the sums are 6, 4, 1, 2, 7, 1. The largest, 7, is the answer for that start index, and it is also the best overall.

    The whole table for the example

    This shows what the running sum holds for each start index i in [-2, -5, 6, -2, -3, 1, 5, -6], as j goes from i to the end, and the best sum of each row:

    i=0: -2 -7 -1 -3 -6 -5 0 -6   best 0
i=1: -5 1 -1 -4 -3 2 -4       best 2
i=2: 6 4 1 2 7 1              best 7
i=3: -2 -5 -4 1 -5            best 1
i=4: -3 -2 3 -3               best 3
i=5: 1 6 0                    best 6
i=6: 5 -1                     best 5
i=7: -6                       best -6

    Each row is built by adding one more element to the previous entry, so no row ever re-adds elements it has already summed. The overall maximum is the largest row maximum, 7, found in row 2. maxSum changes only when a new best appears, so it ends at 7.

    Step by step

    1. Create maxSum, starting at nums[0]. Starting at 0 would be a mistake: if every number is negative, the true answer is negative, and 0 would beat it. nums[0] is itself a subarray, so it is a safe starting value.
    2. Loop over the first index i from 0 to nums.Length - 1.
    3. Declare sum inside that loop and set it to 0. Every new start index begins with an empty subarray, and the variable isn't needed outside the loop.
    4. Loop over the last index j from i to the end, inside the first loop. Starting at i makes the one-element subarray nums[i] the first one tried.
    5. Add nums[j] to sum. This extends the subarray by one element.
    6. Update maxSum in one line with Math.Max, which returns the larger of its two arguments.
    7. Return maxSum after the outer loop has covered every pair.

    The solution in C#

    class Solution {
    public int MaxSumSubarray(int[] nums) {
        int maxSum = nums[0];
        for (int i = 0; i < nums.Length; ++i) {
            int sum = 0;
            for (int j = i; j < nums.Length; ++j) {
                sum += nums[j];
                maxSum = Math.Max(maxSum, sum);
            }
        }
        return maxSum;
    }
};

    The C# details worth noting:

    • nums.Length. Arrays expose their size as the Length property, with no parentheses. (List<T> uses Count instead.)
    • Math.Max. It lives in the System namespace, so code outside the lesson's editor needs using System; at the top of the file. It has overloads for all the numeric types; with two int arguments it returns an int.
    • Scope of sum. A variable declared inside a loop body exists only within that body. Each iteration of the outer loop creates a fresh sum set to 0, which is exactly the reset the algorithm needs.
    • ++i in the loop header. Pre-increment and post-increment behave the same here, because the value of the expression isn't used.
    • Overflow wraps silently. In default C# code, adding past int.MaxValue doesn't throw. The sum wraps around to a negative number. Inputs with huge values would need a long for sum and maxSum. The lesson's tests stay within int.
    • The trailing semicolon. The ; after the class's closing brace is legal in C#, and it does nothing.

    Complexity

    Time: O(n²). The outer loop runs n times. For start index i the inner loop runs n - i times, so the total is n + (n-1) + … + 1, which is n(n+1)/2 and belongs to O(n²). Each inner step is constant work.

    Space: O(1). Just maxSum, sum, i and j. This lesson's brute force is the baseline; later lessons on the same problem improve on the time.

    Edge cases and common mistakes

    • All negative numbers. [-3, -1, -2] returns -1, the best single element. A subarray must contain at least one element, so the empty sum of 0 is not allowed.
    • One element. [4] returns 4.
    • All positive numbers. [1, 2, 3] returns 6, the whole array.
    • Forgetting to reset sum. If sum is declared outside the outer loop, it carries the old total into the next start index, and the sums no longer describe nums[i..j].
    • Starting j at 0 or i + 1. Starting at 0 adds elements before i. Starting at i + 1 never tries the one-element subarray nums[i], which breaks the all-negative case.
    • Empty array. nums[0] throws an IndexOutOfRangeException. The problem assumes at least one element.
    • Not a subsequence. The elements must be adjacent. In [5, -9, 6] the answer is 6, not 11, since 5 and 6 can't be joined without the -9.

    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, -9, 6] gives 6.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free