#6 Maximum Product Subarray

#6 Maximum Product Subarray

Blind 75. Array.

Given an integer array nums, find a subarray that has the largest product, and return the product.The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

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

As usual before we dive into to solve the problem let's understand some real world application of this technique.

Real world use:

1. Facebook/Meta:
2. Identifying sequences of posts that maximize user interaction.
3. Amazon:
4. Finding sequences of products that, when viewed or purchased together, maximize customer satisfaction or revenue.
5. Apple:
6. Health app: Analyzing sequences of health data (like heart rate or step count) to identify periods of peak performance or concerning patterns.
7. Youtube:
8. Optimising playlist by finding sequences of videos that maximize user engagement.
9. Google Maps:
10. Route optimization: Analyzing sequences of traffic data to find the most efficient routes over time.

Now let's disucss how we can solve it?

Patterns we can identify from the question:

1. 1D array
2. Talks about some subarray i.e neighbouring items in the array
3. Find max/min product

thus we want click the idea of implementing Kodane's algorithm.

function maxSubArray(nums){

  let currentProduct = nums[0]

  let maxProduct = nums[0]

  for (let i = 1; i < nums.length;i++){

    currentProduct = Math.max(nums[i], nums[i] * currentProduct)

    maxProduct = Math.max(currentProduct, maxProduct)

  }

  return maxProduct

}

Here the problem we can identify is when a big positive number is multiplied by a negative number max result no longer is the result. Meaning, we cannot handle a negative number with this piece of code.

for example:

   0   1   2

  [-2,  3, -4]

cp = currentProduct, mP = maxProduct

  cP = -2 i.e nums[0]

  mP = -2 .e nums[0]

  cp = Math.max(3, 3 * -2) = 3

  mp = Math.max (-2, 3) = 3

  cp = Math.max(-4 , -4 * 4) = -4

  mp = Math.max(3, -4) =3

  so now let's see how we can handle this situation of -ve number.

• Unlike sum, where a negative number always reduces the sum
• a negative number in a product can potentially increase the product if multiplied by another negative number.

  Positive numbers behavior:

•     When dealing with only positive numbers, keeping track of the maximum product is sufficient. 

  Negative numbers introduce complexity:

•    A negative number can turn a very small (negative) product into a very large (positive) product.
• Conversely, it can turn a very large (positive) product into a very small (negative) product.

Let's see how we can tackle this:

How about having min and max at a point: Why we need both max and min?

•  The maximum product up to the current position might become the minimum product in the next step if multiplied by a negative number.
• The minimum product up to the current position might become the maximum product in the next step if multiplied by a negative number.

Let's look at an example: [-2, 3, -4]

Step 1: num = -2

maxProduct = -2

minProduct = -2

Step 2: num = 3

tempMax = max(3, -2 * 3) = 3

tempMin = min(3, -2 * 3) = -6

maxProduct = 3

minProduct = -6

Step 3: num = -4

tempMax = max(-4, 3 * -4, -6 * -4) = 24 // The min from previous step gives max here

tempMin = min(-4, 3 * -4, -6 * -4) = -12

maxProduct = 24

minProduct = -12

In this example,

• at step 3, the minimum product from step 2 (-6) becomes crucial in calculating the maximum product (24) when multiplied by the next negative number (-4).

By keeping track of both the maximum and minimum products at each step, we ensure that:

• We don't miss the opportunity to flip a very negative product to a very positive one.
• We're prepared for the next number, whether it's positive or negative.

This approach allows us to handle any combination of positive and negative numbers, ensuring we find the true maximum product subarray.

Now refactoring our original kodane's algorithm:

function handleNegativeNum(nums){

  let maxProduct = nums[0]

  let minProduct = nums[0]

  let globalMax = nums[0]

  for(let i = 1; i < nums.length; i++){

    let tempMin = minProduct * nums[i]

    let tempMax = maxProduct * nums[i]

    minProduct = Math.min(nums[i], tempMin, tempMax)

    maxProduct = Math.max(nums[i], tempMin, tempMax )

    globalMax = Math.max(globalMax, minProduct, maxProduct)

  }

  return globalMax

}

This is how we can solve this problem.