Maximize product of a strictly increasing or decreasing subarray
Given an array arr[] of size N, the task is to find the maximum product from any subarray consisting of elements in strictly increasing or decreasing order.
Examples:
Input: arr[] = { 1, 2, 10, 8, 1, 100, 101 }
Output: 10100
Explanation:
Increasing subarray with maximum product is {1, 100, 101}.
Therefore, the required output is 1 * 100 * 101.Input: arr[] = { 1, 5, 7, 2, 10, 12 }
Output: 240
Naive Approach: The simplest approach to solve this problem is to generate all possible subarrays from the given array. For each subarray, check if the elements present in the subarray are either in a strictly increasing or decreasing order or not. If found to be true, then calculate the product of elements of the subarray. Finally, print the maximum product obtained.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient approach The above approach can be optimized by traversing the array and for every increasing or decreasing subarray from the given array, find the maximum product using Kadane’s Algorithm. Finally, print the maximum of all products from increasing or decreasing subarrays. Follow the steps below to solve the problem:
- Initialize a variable, say maxProd, to store the maximum possible product from either an increasing or decreasing subarray from the given array.
- Traverse the array and calculate either the longest increasing or decreasing subarray, say subarray[], whose start index is i.
- Calculate the maximum product of subarray[] using Kadane’s Algorithm for the product, say ProdSub, and update maxProd = max(maxProd, ProdSub).
- Finally, print the value maxProd.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum product of // subarray in the array, arr[] int maxSubarrayProduct(vector< int > arr, int n) { // Maximum positive product // ending at the i-th index int max_ending_here = 1; // Minimum negative product ending // at the current index int min_ending_here = 1; // Maximum product up to // i-th index int max_so_far = 0; // Check if an array element // is positive or not int flag = 0; // Traverse the array for ( int i = 0; i < n; i++) { // If current element // is positive if (arr[i] > 0) { // Update max_ending_here max_ending_here = max_ending_here * arr[i]; // Update min_ending_here min_ending_here = min(min_ending_here * arr[i], 1); // Update flag flag = 1; } // If current element is 0, reset // the start index of subarray else if (arr[i] == 0) { // Update max_ending_here max_ending_here = 1; // Update min_ending_here min_ending_here = 1; } // If current element is negative else { // Stores max_ending_here int temp = max_ending_here; // Update max_ending_here max_ending_here = max(min_ending_here * arr[i], 1); // Update min_ending_here min_ending_here = temp * arr[i]; } // Update max_so_far, if needed if (max_so_far < max_ending_here) max_so_far = max_ending_here; } // If no array elements is positive // and max_so_far is 0 if (flag == 0 && max_so_far == 0) return 0; return max_so_far; } // Function to find the maximum product of either // increasing subarray or the decreasing subarray int findMaxProduct( int * a, int n) { // Stores start index of either increasing // subarray or the decreasing subarray int i = 0; // Initially assume maxProd to be 1 int maxProd = -1e9; // Traverse the array while (i < n) { // Store the longest either increasing // subarray or the decreasing subarray // whose start index is i vector< int > v; v.push_back(a[i]); // Check for increasing subarray if (i < n - 1 && a[i] < a[i + 1]) { // Insert elements of // increasing subarray while (i < n - 1 && a[i] < a[i + 1]) { v.push_back(a[i + 1]); i += 1; } } // Check for decreasing subarray else if (i < n - 1 && a[i] > a[i + 1]) { // Insert elements of // decreasing subarray while (i < n - 1 && a[i] > a[i + 1]) { v.push_back(a[i + 1]); i += 1; } } // Stores maximum subarray product of // current increasing or decreasing // subarray int prod = maxSubarrayProduct(v, v.size()); // Update maxProd maxProd = max(maxProd, prod); // Update i i++; } // Finally print maxProd return maxProd; } // Driver Code int main() { int arr[] = { 1, 2, 10, 8, 1, 100, 101 }; int N = sizeof (arr) / sizeof (arr[0]); cout << findMaxProduct(arr, N); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG { // Function to find the maximum product of // subarray in the array, arr[] static int maxSubarrayProduct(Vector<Integer> arr, int n) { // Maximum positive product // ending at the i-th index int max_ending_here = 1 ; // Minimum negative product ending // at the current index int min_ending_here = 1 ; // Maximum product up to // i-th index int max_so_far = 0 ; // Check if an array element // is positive or not int flag = 0 ; // Traverse the array for ( int i = 0 ; i < n; i++) { // If current element // is positive if (arr.get(i) > 0 ) { // Update max_ending_here max_ending_here = max_ending_here * arr.get(i); // Update min_ending_here min_ending_here = Math.min(min_ending_here * arr.get(i), 1 ); // Update flag flag = 1 ; } // If current element is 0, reset // the start index of subarray else if (arr.get(i) == 0 ) { // Update max_ending_here max_ending_here = 1 ; // Update min_ending_here min_ending_here = 1 ; } // If current element is negative else { // Stores max_ending_here int temp = max_ending_here; // Update max_ending_here max_ending_here = Math.max(min_ending_here * arr.get(i), 1 ); // Update min_ending_here min_ending_here = temp * arr.get(i); } // Update max_so_far, if needed if (max_so_far < max_ending_here) max_so_far = max_ending_here; } // If no array elements is positive // and max_so_far is 0 if (flag == 0 && max_so_far == 0 ) return 0 ; return max_so_far; } // Function to find the maximum product of either // increasing subarray or the decreasing subarray static int findMaxProduct( int [] a, int n) { // Stores start index of either increasing // subarray or the decreasing subarray int i = 0 ; // Initially assume maxProd to be 1 int maxProd = 1 ; // Traverse the array while (i < n) { // Store the longest either increasing // subarray or the decreasing subarray // whose start index is i Vector<Integer> v = new Vector<>(); v.add(a[i]); // Check for increasing subarray if (i < n - 1 && a[i] < a[i + 1 ]) { // Insert elements of // increasing subarray while (i < n - 1 && a[i] < a[i + 1 ]) { v.add(a[i + 1 ]); i += 1 ; } } // Check for decreasing subarray else if (i < n - 1 && a[i] > a[i + 1 ]) { // Insert elements of // decreasing subarray while (i < n - 1 && a[i] > a[i + 1 ]) { v.add(a[i + 1 ]); i += 1 ; } } // Stores maximum subarray product of // current increasing or decreasing // subarray int prod = maxSubarrayProduct(v, v.size()); // Update maxProd maxProd = Math.max(maxProd, prod); // Update i i++; } // Finally print maxProd return maxProd; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 10 , 8 , 1 , 100 , 101 }; int N = arr.length; System.out.print(findMaxProduct(arr, N)); } } // This code contributed by gauravrajput1 |
Python3
# Python3 program to implement # the above approach # Function to find the maximum product # of subarray in the array, arr[] def maxSubarrayProduct(arr, n): # Maximum positive product # ending at the i-th index max_ending_here = 1 # Minimum negative product ending # at the current index min_ending_here = 1 # Maximum product up to # i-th index max_so_far = 0 # Check if an array element # is positive or not flag = 0 # Traverse the array for i in range (n): # If current element # is positive if (arr[i] > 0 ): # Update max_ending_here max_ending_here = max_ending_here * arr[i] # Update min_ending_here min_ending_here = min ( min_ending_here * arr[i], 1 ) # Update flag flag = 1 # If current element is 0, reset # the start index of subarray elif (arr[i] = = 0 ): # Update max_ending_here max_ending_here = 1 # Update min_ending_here min_ending_here = 1 # If current element is negative else : # Stores max_ending_here temp = max_ending_here # Update max_ending_here max_ending_here = max ( min_ending_here * arr[i], 1 ) # Update min_ending_here min_ending_here = temp * arr[i] # Update max_so_far, if needed if (max_so_far < max_ending_here): max_so_far = max_ending_here # If no array elements is positive # and max_so_far is 0 if (flag = = 0 and max_so_far = = 0 ): return 0 return max_so_far # Function to find the maximum product # of either increasing subarray or the # decreasing subarray def findMaxProduct(a, n): # Stores start index of either # increasing subarray or the # decreasing subarray i = 0 # Initially assume maxProd to be 1 maxProd = - 10 * * 9 # Traverse the array while (i < n): # Store the longest either increasing # subarray or the decreasing subarray # whose start index is i v = [] v.append(a[i]) # Check for increasing subarray if i < n - 1 and a[i] < a[i + 1 ]: # Insert elements of # increasing subarray while (i < n - 1 and a[i] < a[i + 1 ]): v.append(a[i + 1 ]) i + = 1 # Check for decreasing subarray elif (i < n - 1 and a[i] > a[i + 1 ]): # Insert elements of # decreasing subarray while (i < n - 1 and a[i] > a[i + 1 ]): v.append(a[i + 1 ]) i + = 1 # Stores maximum subarray product of # current increasing or decreasing # subarray prod = maxSubarrayProduct(v, len (v)) # Update maxProd maxProd = max (maxProd, prod) # Update i i + = 1 # Finally prmaxProd return maxProd # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 10 , 8 , 1 , 100 , 101 ] N = len (arr) print (findMaxProduct(arr, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the maximum product of // subarray in the array, []arr static int maxSubarrayProduct(List< int > arr, int n) { // Maximum positive product // ending at the i-th index int max_ending_here = 1; // Minimum negative product ending // at the current index int min_ending_here = 1; // Maximum product up to // i-th index int max_so_far = 0; // Check if an array element // is positive or not int flag = 0; // Traverse the array for ( int i = 0; i < n; i++) { // If current element // is positive if (arr[i] > 0) { // Update max_ending_here max_ending_here = max_ending_here * arr[i]; // Update min_ending_here min_ending_here = Math.Min(min_ending_here * arr[i], 1); // Update flag flag = 1; } // If current element is 0, reset // the start index of subarray else if (arr[i] == 0) { // Update max_ending_here max_ending_here = 1; // Update min_ending_here min_ending_here = 1; } // If current element is negative else { // Stores max_ending_here int temp = max_ending_here; // Update max_ending_here max_ending_here = Math.Max(min_ending_here * arr[i], 1); // Update min_ending_here min_ending_here = temp * arr[i]; } // Update max_so_far, if needed if (max_so_far < max_ending_here) max_so_far = max_ending_here; } // If no array elements is positive // and max_so_far is 0 if (flag == 0 && max_so_far == 0) return 0; return max_so_far; } // Function to find the maximum product of either // increasing subarray or the decreasing subarray static int findMaxProduct( int [] a, int n) { // Stores start index of either increasing // subarray or the decreasing subarray int i = 0; // Initially assume maxProd to be 1 int maxProd = 1; // Traverse the array while (i < n) { // Store the longest either increasing // subarray or the decreasing subarray // whose start index is i List< int > v = new List< int >(); v.Add(a[i]); // Check for increasing subarray if (i < n - 1 && a[i] < a[i + 1]) { // Insert elements of // increasing subarray while (i < n - 1 && a[i] < a[i + 1]) { v.Add(a[i + 1]); i += 1; } } // Check for decreasing subarray else if (i < n - 1 && a[i] > a[i + 1]) { // Insert elements of // decreasing subarray while (i < n - 1 && a[i] > a[i + 1]) { v.Add(a[i + 1]); i += 1; } } // Stores maximum subarray product of // current increasing or decreasing // subarray int prod = maxSubarrayProduct(v, v.Count); // Update maxProd maxProd = Math.Max(maxProd, prod); // Update i i++; } // Finally print maxProd return maxProd; } // Driver Code public static void Main(String[] args) { int []arr = { 1, 2, 10, 8, 1, 100, 101 }; int N = arr.Length; Console.Write(findMaxProduct(arr, N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> //Javascript program for the above approach // Function to find the maximum product of // subarray in the array, arr[] function maxSubarrayProduct(arr, n) { // Maximum positive product // ending at the i-th index var max_ending_here = 1; // Minimum negative product ending // at the current index var min_ending_here = 1; // Maximum product up to // i-th index var max_so_far = 0; // Check if an array element // is positive or not var flag = 0; // Traverse the array for ( var i = 0; i < n; i++) { // If current element // is positive if (arr[i] > 0) { // Update max_ending_here max_ending_here = max_ending_here * arr[i]; // Update min_ending_here min_ending_here = Math.min(min_ending_here * arr[i], 1); // Update flag flag = 1; } // If current element is 0, reset // the start index of subarray else if (arr[i] == 0) { // Update max_ending_here max_ending_here = 1; // Update min_ending_here min_ending_here = 1; } // If current element is negative else { // Stores max_ending_here var temp = max_ending_here; // Update max_ending_here max_ending_here = Math.max(min_ending_here * arr[i], 1); // Update min_ending_here min_ending_here = temp * arr[i]; } // Update max_so_far, if needed if (max_so_far < max_ending_here) max_so_far = max_ending_here; } // If no array elements is positive // and max_so_far is 0 if (flag == 0 && max_so_far == 0) return 0; return max_so_far; } // Function to find the maximum product of either // increasing subarray or the decreasing subarray function findMaxProduct(a, n) { // Stores start index of either increasing // subarray or the decreasing subarray var i = 0; // Initially assume maxProd to be 1 var maxProd = -1e9; // Traverse the array while (i < n) { // Store the longest either increasing // subarray or the decreasing subarray // whose start index is i var v=[]; v.push(a[i]); // Check for increasing subarray if (i < n - 1 && a[i] < a[i + 1]) { // Insert elements of // increasing subarray while (i < n - 1 && a[i] < a[i + 1]) { v.push(a[i + 1]); i += 1; } } // Check for decreasing subarray else if (i < n - 1 && a[i] > a[i + 1]) { // Insert elements of // decreasing subarray while (i < n - 1 && a[i] > a[i + 1]) { v.push(a[i + 1]); i += 1; } } // Stores maximum subarray product of // current increasing or decreasing // subarray var prod = maxSubarrayProduct(v, v.length); // Update maxProd maxProd = Math.max(maxProd, prod); // Update i i++; } // Finally print maxProd return maxProd; } var arr = [ 1, 2, 10, 8, 1, 100, 101 ]; var N = arr.length; document.write(findMaxProduct(arr, N)); //This code is contributed by SoumikMondal </script> |
10100
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Topic: Subarrays, Subsequences, and Subsets in Array