Start learning free

LESSON 450 OF 539 · DYNAMIC PROGRAMMING

Maximum Product Subarray in C#: Track the Max and the Min in O(n)

Practice O(n) Read the full explanation

Given an array of integers nums, find the subarray with the largest product and return that product.

A subarray is a run of one or more elements that stand next to each other in nums. Its product is all of its elements multiplied together.

Example 1:

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] has the largest product, 2 × 3 = 6. -2 is the only negative number, so every subarray that includes it has a negative product.

Example 2:

Input: nums = [-2, 0, -1]
Output: 0
Explanation: The answer can't be 2: [-2, -1] is not a subarray, because 0 stands between them. The subarray [0] gives 0, and every other subarray gives 0 or less.

Example 3:

Input: nums = [-2, 3, -4]
Output: 24
Explanation: The whole array: the two negative numbers cancel out, -2 × 3 × -4 = 24.

Constraints:

  • 1 <= nums.Length <= 105
  • -10 <= nums[i] <= 10
  • The product of any subarray of nums fits in a 32-bit integer.

Note:

Your algorithm should run in O(n) time and use O(1) extra space, where n is the length of nums.

STEP 1 OF 9
    Ctrl + Enter to check

    C# · DYNAMIC PROGRAMMING

    Maximum Product Subarray in C#, explained

    Problem overview

    MaxProduct receives an int[] nums and returns the largest product of a subarray: one or more elements that stand next to each other, multiplied together. The product of any subarray is guaranteed to fit in an int.

    For [2,3,-2,4] the answer is 6, from [2,3]; the only negative number, -2, makes every subarray that includes it negative. For [-2,0,-1] the answer is 0. It is not 2, because [-2,-1] is not a subarray: the 0 stands between them. For [-2,3,-4] the answer is 24: the two negatives cancel out over the whole array.

    Approach: keep the largest and the smallest product ending here

    For a sum, you would keep only the best subarray ending at each position. A product is trickier, because a negative number turns the most negative product into the most positive one. So the smallest product ending at the previous element can become the largest one at this element. That is why two values are kept for the current position:

    • maxHere: the largest product of a subarray ending at the current element;
    • minHere: the smallest product of a subarray ending at the current element.

    At each new element x, the best subarray ending at x either starts fresh at x or extends the best one ending just before it. Starting fresh is also how a product recovers after a 0, since multiplying by 0 destroys everything before it. If x is negative, swap maxHere and minHere first, because the multiplication flips their order. A third variable, result, remembers the largest maxHere seen. One pass with constant work per element gives O(n) time and O(1) extra space.

    Step by step

    1. maxHere = nums[0]. At the first element, the only subarray ending there is the element itself.
    2. minHere = nums[0]. The smallest product is kept too, since the next negative number may turn it into the largest.
    3. result = nums[0]. A subarray needs at least one element, so the first element alone is a valid start, even if it is negative.
    4. Loop i from 1 while i < nums.Length. Element 0 is already counted.
    5. Negative element: if nums[i] < 0, swap maxHere and minHere with a tuple assignment. After the swap, each variable is the right one to multiply by nums[i].
    6. Update the maximum: maxHere = Math.Max(nums[i], maxHere * nums[i]).
    7. Update the minimum: minHere = Math.Min(nums[i], minHere * nums[i]). This line reads only minHere and nums[i], so it is not affected by the new maxHere computed just before.
    8. Update the answer: result = Math.Max(result, maxHere). The best subarray ends at some element, so checking the best one ending at each element finds it.
    9. Return result.

    The solution in C#

    class Solution {
    public int MaxProduct(int[] nums) {
        int maxHere = nums[0];
        int minHere = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] < 0) {
                (maxHere, minHere) = (minHere, maxHere);
            }
            maxHere = Math.Max(nums[i], maxHere * nums[i]);
            minHere = Math.Min(nums[i], minHere * nums[i]);
            result = Math.Max(result, maxHere);
        }
        return result;
    }
}

    C# details worth knowing:

    • Tuple swap. (maxHere, minHere) = (minHere, maxHere); builds a pair from the right-hand values and then assigns its parts to the left-hand variables. The right side is evaluated completely first, so no temporary variable is needed. This is a feature of C# 7 and later.
    • Math.Max and Math.Min take two numbers of the same type and return one. They live in System, and C# method names are PascalCase.
    • int overflow wraps silently in the default unchecked context. The lesson guarantees that every subarray product fits in an int, but maxHere and minHere are also products of subarrays, so they fit too. For arrays without that guarantee, long would be the safer type. A constant expression such as int.MaxValue * 2 is a compile error (CS0220), but a product of variables, such as 100000 * 100000 held in two int variables, simply wraps, giving 1410065408.
    • nums[0] needs a non-empty array. An empty array would throw IndexOutOfRangeException. The lesson guarantees at least one element.

    Complexity

    Time: O(n). The loop visits each element once, and each visit does a few multiplications and comparisons.

    Space: O(1). Three int variables, whatever the length of nums.

    Edge cases and common mistakes

    • A single negative number. [-3] returns -3. Starting result at 0 would wrongly return 0.
    • Zeros split the array. For [-2,3,-4,0,5] the answer is 24, from the part before the 0. Because each step can start fresh at nums[i], the run after the 0 starts clean, and [0,2] returns 2.
    • Two negatives. A negative maxHere turns into the answer when another negative arrives: at [-2,3,-4] the minimum -6 times -4 gives 24.
    • Keeping only maxHere. This fails on [-2,3,-4], where the best product comes from the most negative one before the second negative number.
    • Forgetting the swap, or doing it after the multiplications. The variables would then multiply by the wrong partner, and the maximum and minimum would be mixed up when nums[i] is negative.
    • Starting the loop at 0. Element 0 would be multiplied into itself, squaring it.

    Testing

    Printing the three values after each step shows how the swap works. For [2,3,-2,4]:

    start       max=2   min=2
i=1  x=3    max=6   min=3    result=6
i=2  x=-2   max=-2  min=-12  result=6
i=3  x=4    max=4   min=-48  result=6

    For [-2,3,-4]:

    start       max=-2  min=-2
i=1  x=3    max=3   min=-6   result=3
i=2  x=-4   max=24  min=-12  result=24

    Other inputs and the results of MaxProduct:

    numsResult
    [-2,0,-1]0
    [-3]-3
    [0,2]2
    [-2,3,-4,0,5]24
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free