Posts Max Product Subarray
Post
Cancel

Max Product Subarray

Problem Description

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.

leetcode

Solution

Since the array can contain negative numbers also, we need to main currentMax as well as currentMin. Because if there are even number of negative numbers in the subarray, the product will be positive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {

    public int maxProduct(int[] nums) {

        int n = nums.length;

        int currentMax=nums[0];
        int currentMin=nums[0];

        int ans = currentMax;

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

            //tempMax = max(currentElement or currentMax*currentElement or currentMin*currentElement)
            int tempMax = Math.max(nums[i], Math.max(currentMax*nums[i], currentMin*nums[i]));

            //tempMin = min(currentElement or currentMax*currentElement or currentMin*currentElement)
            int tempMin = Math.min(nums[i], Math.min(currentMax*nums[i], currentMin*nums[i]));
            
            currentMax = tempMax;
            currentMin = tempMin;

            ans = Math.max(ans, currentMax);

        }

        return ans;
    }
}
This post is licensed under CC BY 4.0 by the author.