Start learning free

LESSON 208 OF 347 · PARTIAL SUMS #1

Maximum Sum Subarray in C#: O(n) with Kadane's Algorithm

Practice O(n) Read the full explanation

( Kadane's Algorithm )


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 O(1) extra space.


STEP 1 OF 6
    Ctrl + Enter to check

    C# · PARTIAL SUMS #1

    Maximum Sum Subarray in C#, explained

    Problem overview

    The method MaxSumSubarray receives an int[] that may contain negative and positive numbers. It returns the largest sum that any continuous stretch of the array can have. The stretch must contain at least one element.

    For [-2, -5, 6, -2, -3, 1, 5, -6] the best stretch is [6, -2, -3, 1, 5], whose sum is 7. The statement asks for O(n) time and O(1) extra space, so the method must make one pass and keep only a few variables.

    Approach: the best subarray ending here

    Checking every start and end position costs at least O(n²). Kadane's algorithm gets to O(n) with one question for each element: what is the largest sum of a subarray that ends at this element?

    That subarray is either the element alone, or the element appended to the best subarray ending at the previous position. Extending only helps when the previous best is positive. A negative running sum just drags the total down, so it is better to start fresh. This gives the recurrence:

    maxSum = val + max(maxSum, 0)

    The overall answer is the largest maxSum seen at any position, because the best subarray has to end somewhere.

    Tracing [-2, -5, 6, -2, -3, 1, 5, -6], the pairs of maxSum and result after each element are: -2 and -2, then -5 and -2, then 6 and 6, then 4 and 6, then 1 and 6, then 2 and 6, then 7 and 7, then 1 and 7. The -5 is not attached to the earlier -2, and the 6 starts a fresh subarray because the previous maxSum was negative. The answer is 7.

    Step by step

    1. Initialise result with nums[0]. It must start at a sum that some subarray really has. Starting at 0 is wrong when every number is negative, because the empty subarray isn't allowed and the answer is then negative.
    2. Initialise maxSum with 0. It stands for the best sum ending at the previous element. Before the first element there is nothing, which behaves like 0.
    3. Loop over the elements with a foreach, reading each one as val.
    4. Update maxSum with the recurrence: val + Math.Max(maxSum, 0). Either extend the previous best or start over.
    5. Update result with Math.Max(result, maxSum), since maxSum is now the best sum ending at this element.
    6. Return result once the loop is done.

    The solution in C#

    class Solution {

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

    The C# details to notice:

    • foreach over an array. foreach (int val in nums) reads each element in order, with no index to manage. The loop variable val is read-only inside the loop, which is fine because the code never assigns to it.
    • Math.Max with int arguments returns an int, so no casts are needed.
    • Silent overflow. int arithmetic wraps around without an error by default. For arrays whose sums could exceed about 2.1 billion, make maxSum and result long. For modest values, int is enough.
    • The input isn't modified. Unlike the sorting lessons, this method only reads nums.

    Complexity

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

    Space: O(1). Two integer variables, whatever the input size.

    Edge cases and common mistakes

    • All negative numbers. [-3, -1, -2] gives -1, the largest single element. This is why result starts at nums[0] and not 0.
    • A single element. [4] gives 4.
    • All positive numbers. [1, 2, 3] gives 6, the sum of the whole array, because maxSum never resets.
    • Resetting to 0 instead of to val. Writing maxSum = Math.Max(maxSum + val, 0) forces every running sum to be at least 0 and fails on all-negative arrays. The lesson's form keeps val itself when starting fresh.
    • Updating result before maxSum. The result would then lag one element behind.
    • 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