{"post":"

Input: [2,3,-2,4]
\nOutput: 6

The Maximum Product Sub-Array problem asks the user to find the subarray with the largest possible product. Sounds, Easy right?

The catch is to calculate the highest product keeping in mind that the array size can vary, as well as the fact that the locations have to be contiguous. This is explained simply below:

Again, we employ two approaches to solve this problem:

1. Brute Force
\n2. Divide and Conquer
\nThere also exists a third way, which is known as Kadane’s Algorithm, but we won’t go into that in this section.

# Approach 1: Brute force
\nIn Brute force, the pseudo-code is to:

Find all the possible subarrays
Find the maximum.

Code:

\nvoid MaxProductSubArray( int * a, int size)\n{ int MaxProduct = a[0];\n  int MaxProductStart = 0, MaxProductEnd = 0;\nfor( int i = 1; i < size; i++) { int tempProduct = 0; int j = i; while(j>=0)\n{ tempProduct *= a[j];\nif ( tempProduct > MaxProduct )\n{ MaxProduct = tempProduct;\nMaxProductStart = j;\nMaxProductEnd = i;\n}\nj--;\n}  );\ncout << \"Max Product in the array : \" << MaxProduct << endl;\ncout << \"Max Product Start : \" << MaxProductStart << \" MaxProductEnd : \" << MaxProductEnd << endl;\n}\n

# APPROACH 2: Optimized Approach
\nHere, the idea is to traverse array from left to right keeping two variables minEnd and maxEnd which represents the minimum and maximum product value till the ith index of the array. Now, if the ith element of the array is negative that means now the values of minEnd and maxEnd will be swapped as value of maxEnd will become minimum by multiplying it with a negative number. Now, compare the minEnd and maxEnd.

The value of minEnd and maxEnd depends on the current index element or the product of the current index element and the previous minEnd and maxEnd respectively

Code:

\n#include <bits/stdc++.h> \nusing namespace std; \nint maxSubarray(int givenArray[], int n)\n{\nint minEnd = 1;
\nint minEnd = 1; \n\nint maxSoFar = 1; \nint flag = 0; \nfor (int i = 0; i &lt; n; i++) { if (givenArray[i] &gt; 0) { \n        minEnd = minEnd * givenArray[i]; \n        minEnd = min(minEnd * givenArray[i], 1); \n        flag = 1; \n    } \n\n    else if (givenArray[i] == 0) { \n        minEnd = 1; \n        minEnd = 1; \n    } \n      else { \n        int temp = minEnd; \n        minEnd = max(minEnd * givenArray[i], 1); \n        minEnd = temp * givenArray[i]; \n    } \n\n    if (maxSoFar &lt; minEnd) \n        maxSoFar = minEnd; \n} \nif (flag == 0 && maxSoFar == 1) \n    return 0; \nreturn maxSoFar; \n
\n}
\nint main()\n{\nint givenArray[] = { 12, 4234, 34234, -21,-231,-1};\nint n = sizeof(givenArray) / sizeof(givenArray[0]);\ncout << \"Maximum Sub givenArray product is \"\n<< maxSubarray(givenArray, n);\nreturn 0;\n}\n

This is how the Maximum product Subarray problem is solved.

\n","title":"Maximum Product Sub-array Problem","authorDetails":{"name":"studymite","slug":"admin"},"description":"The Maximum Product Sub-Array problem asks the user to find the subarray with the largest possible product. This can be solved with Divide and Conquer and kadane's algorithm.","slug":"maximum-product-sub-array-problem/","articleId":"636a83447bb1ce5072622b96","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}