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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// ============================================================================ // Author: Kenneth Perkins // Date: Dec 2, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find maximum product contiguous subarray // ============================================================================ public class Solution { public int MaxProduct(int[] nums) { // Store the result var result = nums[0]; // The current maximum and minimum product of the subarray var currentMin = nums[0]; var currentMax = nums[0]; for (int index = 1; index < nums.Length; ++index) { // Swap current max/min 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 if (nums[index] < 0) { var temp = currentMax; currentMax = currentMin; currentMin = temp; } // Determine the max/min product for the current number. // It is either the current number itself // or the max/min by the previous values times the current one currentMax = Math.Max(nums[index], currentMax * nums[index]); currentMin = Math.Min(nums[index], currentMin * nums[index]); // Keep track of the current max result result = Math.Max(result, currentMax); } return result; } }// http://programmingnotes.org/ |
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
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply