Subarray With Maximum Product

#include<bits/stdc++.h>

using namespace std;

int subarrayWithMaxProduct(vector<int> &arr){

    // Write your code here.

    int prod1 = arr[0], prod2 = arr[0], result = arr[0];

    int n = arr.size();

    for(int i=1; i<n; i++){

          int temp = max({arr[i], prod1*arr[i], prod2*arr[i]});

          prod2 = min({arr[i], prod1*arr[i], prod2*arr[i]});

          prod1 = temp;

          result = max(result, prod1);

        }

    return result;

}

#include<vector>

#include <climits> // Include this header for INT_MIN

int subarrayWithMaxProduct(vector<int> &arr) {

  int ans = INT_MIN;

  int pref = 1; int suff = 1; 

  int n = arr.size();

  for (int i = 0; i < n; i++){

    if(pref == 0) pref = 1;

    if(suff == 1) suff = 1; 

    pref = pref * arr[i]; 

    suff = suff * arr[n-i-1]; 

    ans = max(ans, max(pref, suff));

  }

  return ans; 

}

/*I hope this approach is right, regardless of this solution getting AC.*/

int subarrayWithMaxProduct(vector<int> &arr){
    // Write your code here.
    //{-2, 3, -4, 0} ans = 24(-2*3*-4)
    int productSoFar = 1, positiveProductSoFar = 1, maxProduct = INT_MIN, ansSoFar = 1;
    for(auto n: arr)
    {
        productSoFar *= n;
        positiveProductSoFar *= n;
        ansSoFar = max(n, max(productSoFar, positiveProductSoFar));
        maxProduct = max(maxProduct, ansSoFar);


        if(productSoFar == 0)
            productSoFar = 1;
        if(positiveProductSoFar <= 0)
            positiveProductSoFar = 1;
    }
    return maxProduct;
}

#include<bits/stdc++.h>

int subarrayWithMaxProduct(vector<int> &arr){

//  // Write your code here.

//  int maxi=INT_MIN;

//  for(int i=0;i<arr.size();i++){

//      int prod=1;

//      for(int j=i;j<arr.size();j++){

// prod=prod*arr[j];

// maxi=max(prod,maxi);

//      }

//  }

//  return maxi;                //O(n^2)

//------------------------

int pre=1,suff=1;

int ans=INT_MIN;

int n=arr.size();

for(int i=0;i<n;i++){

    if(pre==0)pre=1;

    if(suff==0)suff=1;

    pre=pre*arr[i];

    suff=suff*arr[n-i-1];

    ans=max(ans,max(pre,suff));

}

return ans;

}

//O(n)=TC, SC=O(1)

The idea is to find the maximum product of a subarray in the given array of integers. This problem can be tricky because negative numbers can flip the product, and we may have to consider both the prefix (left to right) and suffix (right to left) arrays to make sure we don't miss any potential maximum product.

1. Two Traversals: Instead of maintaining only one running product, we maintain two:

One for the prefix product, going from left to right.

Another for the suffix product, going from right to left.

Reset on Zero: Since a product becomes 0 when any element is zero, we reset the product to 1 when encountering a zero.

Keep Track of Max Product: During each traversal, we keep updating the maximum product encountered so far.

We keep two products:

Prefix: Starts multiplying numbers from the left.

Suffix: Starts multiplying numbers from the right.

At each step, we check the product of both the prefix and suffix and update the maximum product found.

If we encounter a zero, the product will be reset to 1, since multiplying by zero ruins the subarray product.

• Time complexity:

O(n): We are making only a single pass through the array, which means the time complexity is linear.

• Space complexity:

O(1): We only use a few extra variables (prefix, suffix, max), so the space complexity is constant.

public class Solution {
    public static int subarrayWithMaxProduct(int []arr){
        // Write your code here.
        int n=arr.length;
        int prefix=1;
        int suffix=1;
        int max=Integer.MIN_VALUE;
        for(int i=0;i<n;i++)
        {
            if(prefix==0)
            prefix=1;
            else if(suffix==0)
            suffix=1;

            suffix=suffix*arr[i];
            prefix=prefix*arr[n-i-1];
            max=Math.max(max,Math.max(prefix,suffix));
        }
        return max;
    }
}

#include<vector>

#include <bits/stdc++.h>

int subarrayWithMaxProduct(vector<int> &arr){

    // Write your code here.

    int prefix = 1;

    int suffix = 1;

    int ans = INT_MIN;

    int  n = arr.size();

    for(int i = 0; i < n ; i++){

        if(prefix == 0) prefix= 1;

        if(suffix == 0) suffix = 1;

        prefix = prefix * arr[i];

        suffix = suffix * arr[n-i-1];

        ans = max(ans , max(prefix,suffix));

    }

    return ans;

}

#include<vector>

#include<stdio.h>

int subarrayWithMaxProduct(vector<int> &arr){

    // Write your code here.

    int n = arr.size();

    int ans = 0;

    int pre = 1 , suff = 1;

    for(int i=0 ; i<n ; i++){

        if(pre == 0) pre =1;

        if(suff == 0) suff =1;

        pre = pre*arr[i];

        suff = suff*arr[n-i-1];

        ans = max(ans , max(pre , suff));

    }

    return ans;

}

#include<bits/stdc++.h>

int subarrayWithMaxProduct(vector<int> &arr){

    int pre=1,suff=1;

    int n = arr.size();

    int ans = INT_MIN;

    for(int i=0;i<n;i++) {

        pre = pre*arr[i];

        suff = suff*arr[n-i-1];

        if(pre == 0) pre = 1;

        if(suff == 0) suff = 1;

        ans = max(ans,max(pre,suff));

    }

    return ans;

}

#include <climits>

int subarrayWithMaxProduct(vector<int> &arr){

// Write your code here.

int prefi=1;

int suf=1;

int maxi=INT_MIN;

int n=arr.size();

for(int i=0;i<arr.size();i++)

{

if(prefi==0) prefi=1;

if(suf==0) suf=1;

prefi=prefi*arr[i];

suf=suf*arr[n-i-1];

maxi=max(maxi,max(prefi,suf));

}

return maxi;

}

import java.util.*;

public class Solution {

    public static int subarrayWithMaxProduct(int []arr){

        // Write your code here.

        int ans = Integer.MIN_VALUE;

        int n = arr.length;

        int pre =1, suff =1;

        for(int  i = 0 ;i< n;i++){

            if(pre == 0) pre =1;

            if(suff == 0 ) suff = 1;

            pre = pre *arr[i];

            suff = suff * arr[n-i-1];

            ans = Math.max(ans,Math.max(pre,suff));

        }

        return ans;

    }

}