prob.( array ) maxproduct of a subarray. |java| complete concept and approach,CODE

  RAHUL CHOUDHARY (IIT BHU)

Problem.

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.

Intuition:

The code aims to find the maximum product of any subarray within the given nums array. The approach is based on dynamic programming, where at each iteration, we update the current minimum product (currMin), current maximum product (currMax), and the global maximum product (maxglobal).

Approach:

1. First, we perform some basic checks:
   • If the nums array is null or empty, we throw an IllegalArgumentException.
2. We initialize three variables:
   • minProd: Represents the current minimum product.
   • maxProd: Represents the current maximum product.
   • maxglobal: Represents the global maximum product.
   • We initialize all three variables with the value of the first element of the nums array.
3. We iterate through the nums array starting from the second element (index 1).
4. For each iteration:
   • We calculate the current minimum product (currMin) by taking the minimum of the current number (nums[i]), the product of the current number and the previous minimum product (minProd * nums[i]), and the product of the current number and the previous maximum product (maxProd * nums[i]).
   • We calculate the current maximum product (currMax) by taking the maximum of the current number (nums[i]), the product of the current number and the previous minimum product (minProd * nums[i]), and the product of the current number and the previous maximum product (maxProd * nums[i]).
   • We update the minProd and maxProd variables with the values of currMin and currMax, respectively.
   • We update the maxglobal variable by taking the maximum of the current maxglobal and maxProd.
5. After the iteration, we have the maximum product of any subarray stored in the maxglobal variable.
6. We return the value of maxglobal as the result.

Complexity:

• Time complexity: O(n), where n is the length of the nums array. We iterate through the array once.
• Space complexity: O(1). We use a constant amount of extra space to store the variables minProd, maxProd, and maxglobal, regardless of the size of the input nums array.

//code

class Solution {

public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) { throw new IllegalArgumentException("Input array cannot be null or empty."); } int minProd = nums[0]; int maxProd = nums[0]; int maxglobal = nums[0]; for (int i = 1; i < nums.length; i++) { int currMin = Math.min(nums[i], Math.min(minProd * nums[i], maxProd * nums[i])); int currMax = Math.max(nums[i], Math.max(minProd * nums[i], maxProd * nums[i])); minProd = currMin; maxProd = currMax; maxglobal = Math.max(maxglobal, maxProd); } return maxglobal; } }