🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

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

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

Solution:

You must go through the chapter on Kadane's Algorithm first before solving this problem. I highly recommend you to try to solve this problem using Kadane's Algorithm on your own before looking at the solution below.

We would use the same concept of local maxima and global maxima as in Kadane's Algorithm to solve this problem.

Using the concept of local maxima and global maxima and keeping Kadane's Algorithm technique in mind, we can make the below few observations:

• Any element in the given array of integers can be either (1) greater than zero, (2) less than zero, or (3) equal to zero.
  
• Lets suppose there are two given integer arrays as below:
  arr1 = {-2, 4, 6}, for which maximum product subarray is {4, 6} with maximum product 24
  arr2 = {-2, 4, -6}, for which the maximum product subarray is {-2, 4, -6} with maximum product 48.
  
  The two given arrays arr1 and arr2 have first two items same but when we are processing 3^rd element for arr1 we are taking local maxima so far = 4
  but, for arr2 we are taking local maxima so far = (-2 * 4) = -8, because that gives the maximum product subarray since arr2[2] < 0.
  
  So gives us a very important insight about a very important aspect as to how to design the solution for this problem: we need to keep track of both positive and negative local maxima, wherever and whenever applicable. At any point of time we need to keep track of negative and positive local maxima (if available) because we do not know what the next element would be: zero, positive or negative.
  
• Let's say arr[] is the given array of integers and let's say we are currently at the i^th element of the given array of integers.
  Let's suppose, arr[i] < 0
  
  Since we are interested in product and we can have both positive and negative integers, the local maxima and global maxima can be negative, positive or zero. Local maxima gives current maxima for contiguous subarray.
  If local maxima is so far is negative, then we multiply it with arr[i] which is also negative giving us new local maxima which is positive, since when we multiply two negative integers we get a positive integer.
  
  On the other hand, if the local maxima so far is positive then new local maxima becomes negative.
  
• Now let's suppose, arr[i] >= 0
  If local maxima so far is zero or less then the new local maxima becomes arr[i].
  If local maxima so far is greater than zero then new local maxima would be product os arr[i] and local maxima so far.

The above discussion helps us come up with the below code. I have discussed the algorithm and implementation logic in the inline comments in the code below.

Java Solution:

Login to Access Content

Python Soluton:

Login to Access Content

Instructor: