C# || Maximum Product Subarray – How To Find Largest Product In Contiguous Subarray Using C#

The following is a module with functions which demonstrates how to find the largest product in a contiguous subarray using C#.


1. Max Product – Problem Statement

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:


Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:


Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.


2. Max Product – Solution

The following is a solution which demonstrates how to find the largest product in a contiguous subarray.

This solution is inspired by Kadane’s algorithm to find the result.

The idea here is similar to the ‘Maximum Subarray‘ problem.

In this solution, we have two values:

  • The current cumulative maximum product up to current element
  • The current cumulative minimum product up to current element

Each loop iteration, these values are updated by either multiplying the new element at the current index with the existing product, or starting fresh from current index.

When a negative number is encountered, the current max and current min values are swapped, because multiplying a negative number makes a big number smaller, and multiplying a negative number makes small number bigger. So their intent is redefined by swapping.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


6
0

Was this article helpful?
👍 YesNo

Leave a Reply