Start learning free

LESSON 209 OF 347 · PARTIAL SUMS #1

Maximum Sum Subarray in C#: 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

    C# · PARTIAL SUMS #1

    Maximum Sum Subarray in C#, explained

    Problem overview

    The method MaxSumSubarray receives an int[] with positive and negative numbers and returns the largest sum of any continuous, non-empty subarray. For [-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) time and at most O(n) extra space.

    Approach: a subarray sum is a difference of prefix sums

    The prefix sum at position i is the sum of all elements up to and including i. The sum of a subarray from l to r equals the prefix sum at r minus the prefix sum just before l. The empty prefix has the sum 0.

    So the largest subarray sum ending at element r is the prefix sum at r minus the smallest earlier prefix sum, the empty prefix included. Taking the best over all r gives the answer. Instead of storing all prefix sums in an array, it is enough to keep the running one, partialSum, and the smallest one seen so far, minSum.

    The trace on the example lists the three values after each element: partialSum, minSum and result. They are -2, -2 and -2 for the first element, then -7, -7 and -2, then -1, -7 and 6, then -3, -7 and 6, then -6, -7 and 6, then -5, -7 and 6, then 0, -7 and 7, and finally -6, -7 and 7. At the seventh element, partialSum is 0 and minSum is -7, so the best subarray ending there sums to 0 - (-7) = 7. That subarray starts right after the point where the prefix sum was lowest: the elements 6, -2, -3, 1 and 5.

    The statement says at most O(n) space because the idea is usually explained with a full prefix array. Keeping just two numbers brings the extra space down to O(1).

    Step by step

    1. Declare partialSum and minSum, both 0. The prefix before any element is empty and has the sum 0, so it's the first candidate for the smallest prefix.
    2. Initialise result with nums[0]. It has to be a sum some subarray really has. Starting at 0 would be wrong for arrays of negative numbers only.
    3. Loop over the elements with foreach, reading each as val.
    4. Extend the running sum: partialSum += val.
    5. Update result. The best subarray ending here has the sum partialSum - minSum, so take Math.Max(result, partialSum - minSum).
    6. Update minSum with Math.Min(minSum, partialSum), so the next element can use this prefix as a starting point.
    7. Return result after the loop.

    The order of steps 5 and 6 matters. result must be updated before minSum takes the current prefix into account. Otherwise the subarray would start after the current element and end at it, which is empty.

    The solution in C#

    class Solution {

    public int MaxSumSubarray(int[] nums) {
        int partialSum = 0, minSum = 0;
        int result = nums[0];
        foreach (int val in nums) {
            partialSum += val;
            result = Math.Max(result, partialSum - minSum);
            minSum = Math.Min(minSum, partialSum);
        }
        return result;
    }
};

    The C# details to notice:

    • Declaring two variables together. int partialSum = 0, minSum = 0; declares two separate int variables, each with its own initial value.
    • += adds to the variable and stores the result back in it.
    • Silent overflow. int sums wrap around without an error by default. If the prefix sums could pass roughly 2.1 billion, declare partialSum, minSum and result as long.
    • The closing }; after the class is legal. An extra semicolon after a type declaration is allowed in C#.

    Complexity

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

    Space: O(1). Three integer variables. A version that stores the whole prefix array would use O(n), which the statement allows.

    Edge cases and common mistakes

    • All negative numbers. [-3, -1, -2] gives -1. The best subarray is the single element -1, and the method finds it at the second position: the prefix sum is -4 and the smallest earlier prefix is -3, so the difference is -1.
    • A single element. [4] gives 4, from the prefix 4 minus the empty prefix 0.
    • All positive numbers. [1, 2, 3] gives 6, because minSum stays 0 and the full prefix sum is the biggest.
    • Starting minSum too high. Initialising it with nums[0] or a large value would exclude the empty prefix, so subarrays that begin at index 0 couldn't be measured.
    • Updating minSum first. It would let a subarray end where it started and subtract the current prefix from itself, which gives 0 and is wrong when every number is negative.
    • Empty array. nums[0] would throw IndexOutOfRangeException. The problem assumes at least one element.

    Testing

    • [-2, -5, 6, -2, -3, 1, 5, -6] gives 7.
    • [-3, -1, -2] gives -1.
    • [4] gives 4.
    • [1, 2, 3] 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