Problem Statement:
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.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10- The product of any subarray of
numsis guaranteed to fit in a 32-bit integer.
Approach:
- Initialize Variables
ltrProd = 1→ product when traversing left to right.rtlProd = 1→ product when traversing right to left.finalMax = -Infinity→ to keep track of the maximum product found.
- Two-way traversal logic
- Since the
maximum product subarraycan break due to negative numbers and zeros, we handle it by multiplying in both directions:- LTR (left-to-right): multiply each element into
ltrProd. - RTL (right-to-left): multiply each element from the back into
rtlProd.
- LTR (left-to-right): multiply each element into
- Since the
- Update maximum, After each step, check the maximum value among
finalMax,ltrProd, andrtlProd. - Handle zero reset
- If at any point the product becomes
0, reset it to1. - This is because any product involving
0will be0, but a new subarray can start after zero.
- If at any point the product becomes
- After completing the single loop, finalMax will contain the
maximum product subarray.
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(1)
Dry Run
Input: arr = [2, 3, -2, 4]
Initial: n = 4 ltrProd = 1, rtlProd = 1 finalMax = -Infinity i = 0: ltrProd = 1 * 2 = 2 rtlProd = 1 * arr[3] = 1 * 4 = 4 finalMax = max(-∞, 2, 4) = 4 i = 1: ltrProd = 2 * 3 = 6 rtlProd = 4 * arr[2] = 4 * -2 = -8 finalMax = max(4, 6, -8) = 6 i = 2: ltrProd = 6 * -2 = -12 rtlProd = -8 * arr[1] = -8 * 3 = -24 finalMax = max(6, -12, -24) = 6 i = 3: ltrProd = -12 * 4 = -48 rtlProd = -24 * arr[0] = -24 * 2 = -48 finalMax = max(6, -48, -48) = 6 Loop ends Return finalMax = 6
Output: 6
var maxProduct = function(arr) {
let n = arr.length;
let ltrProd = 1, rtlProd = 1;
let finalMax = -Infinity;
for (let i = 0; i < n; i++) {
ltrProd = ltrProd * arr[i];
rtlProd = rtlProd * arr[n - i - 1];
finalMax = Math.max(finalMax, ltrProd, rtlProd);
if (ltrProd === 0) ltrProd = 1;
if (rtlProd === 0) rtlProd = 1;
}
return finalMax;
};
def maxProduct(arr):
n = len(arr)
ltrProd = 1
rtlProd = 1
finalMax = float('-inf')
for i in range(n):
ltrProd *= arr[i]
rtlProd *= arr[n - i - 1]
finalMax = max(finalMax, ltrProd, rtlProd)
if ltrProd == 0:
ltrProd = 1
if rtlProd == 0:
rtlProd = 1
return finalMax
if __name__ == "__main__":
arr = [2, -3, 4, 0, -2, -1]
print("Max product:", maxProduct(arr))
public class MaxProduct {
public static long maxProduct(int[] arr) {
int n = arr.length;
long ltrProd = 1, rtlProd = 1;
long finalMax = Long.MIN_VALUE;
for (int i = 0; i < n; i++) {
ltrProd *= arr[i];
rtlProd *= arr[n - i - 1];
finalMax = Math.max(finalMax, Math.max(ltrProd, rtlProd));
if (ltrProd == 0) ltrProd = 1;
if (rtlProd == 0) rtlProd = 1;
}
return finalMax;
}
public static void main(String[] args) {
int[] arr = {2, -3, 4, 0, -2, -1};
System.out.println("Max product: " + maxProduct(arr));
}
}
#include <bits/stdc++.h>
using namespace std;
long long maxProduct(const vector& arr) {
int n = arr.size();
long long ltrProd = 1, rtlProd = 1;
long long finalMax = LLONG_MIN;
for (int i = 0; i < n; ++i) {
ltrProd *= arr[i];
rtlProd *= arr[n - i - 1];
finalMax = max(finalMax, max(ltrProd, rtlProd));
if (ltrProd == 0) ltrProd = 1;
if (rtlProd == 0) rtlProd = 1;
}
return finalMax;
}
int main() {
vector arr = {2, -3, 4, 0, -2, -1};
cout << "Max product: " << maxProduct(arr) << endl;
return 0;
}
#include <stdio.h>
#include <limits.h>
long long maxProduct(int *arr, int n) {
long long ltrProd = 1, rtlProd = 1;
long long finalMax = LLONG_MIN;
for (int i = 0; i < n; ++i) {
ltrProd *= arr[i];
rtlProd *= arr[n - i - 1];
if (ltrProd > finalMax) finalMax = ltrProd;
if (rtlProd > finalMax) finalMax = rtlProd;
if (ltrProd == 0) ltrProd = 1;
if (rtlProd == 0) rtlProd = 1;
}
return finalMax;
}
int main() {
int arr[] = {2, -3, 4, 0, -2, -1};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Max product: %lld\n", maxProduct(arr, n));
return 0;
}
using System;
class Program {
static long MaxProduct(int[] arr) {
int n = arr.Length;
long ltrProd = 1, rtlProd = 1;
long finalMax = long.MinValue;
for (int i = 0; i < n; i++) {
ltrProd *= arr[i];
rtlProd *= arr[n - i - 1];
finalMax = Math.Max(finalMax, Math.Max(ltrProd, rtlProd));
if (ltrProd == 0) ltrProd = 1;
if (rtlProd == 0) rtlProd = 1;
}
return finalMax;
}
static void Main() {
int[] arr = {2, -3, 4, 0, -2, -1};
Console.WriteLine("Max product: " + MaxProduct(arr));
}
}
