Given a list arr[] consisting of arrays of varying lengths, the task is to find the maximum product that can be formed by taking exactly one element from each array present in the list.
Examples:
Input: arr[] = {{-3, -4}, {1, 2, -3}}
Output: 12
Explanation:
Pick -4 from the first array and -3 from the second array.
Therefore, maximum possible product is 12.Input: arr[] = {{1, -1}, {2, 3}, {10, -100, 20}}
Output: 300
Explanation:
Pick -1 from the first array and 3 from the second array and -100 from the third array.
Therefore, maximum product is 300.
Naive Approach: The simplest approach to solve this problem is to find each possible combination of elements by taking one element from each array of the list using Recursion and select the maximum product out of all possible combinations.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the maximum product int maximum = -INT_MAX; // Function to find maximum product // possible by taking exactly one element // from each array of the list void calculateProduct(vector<vector<int> > &List, int index, int product) { // If last index is encountered if(index + 1 == List.size()) { for (int i :List[index]) { // Find the maximum product maximum = max(maximum, product *i); } // Otherwise, recursively calculate // maximum product for every element } else { for(int i: List[index]) calculateProduct(List, index + 1, product * i); } } // Driver Code // Count of given arrays int main() { int N = 2; // Given list of N arrays vector<vector<int> > arr = {{-3, -4}, {1, 2, -3}}; // Calculates the maximum // possible product calculateProduct(arr, 0, 1); // Print the maximum product cout << maximum; return 0; } // This code is contributed by mohit kumar 29 |
Java
// Java program for the // above approach import java.util.*; class GFG{ static int maximum = -Integer.MAX_VALUE; // Function to find maximum product // possible by taking exactly one element // from each array of the list static void calculateProduct(int[][] List, int index, int product) { // If last index is encountered if (index + 1 == List.length) { for(int i:List[index]) { // Find the maximum product maximum = Math.max(maximum, product * i); } // Otherwise, recursively calculate // maximum product for every element } else { for(int i:List[index]) calculateProduct(List, index + 1, product * i); } } // Driver Code public static void main(String[] args) { int N = 2; // Given list of N arrays int[][] arr = { { -3, -4 }, { 1, 2, -3 } }; // Calculates the maximum // possible product calculateProduct(arr, 0, 1); // Print the maximum product System.out.print(maximum); } } // This code is contributed by code_hunt |
Python3
# Python program for the above approach # Stores the maximum product maximum = -float('INF') # Function to find maximum product # possible by taking exactly one element # from each array of the list def calculateProduct(List, index, product): # If last index is encountered if(index + 1 == len(List)): for i in List[index]: global maximum # Find the maximum product maximum = max(maximum, product * i) # Otherwise, recursively calculate # maximum product for every element else: for i in List[index]: calculateProduct(List, index + 1, product * i) # Driver Code # Count of given arrays N = 2 # Given list of N arrays arr = [[-3, -4], [1, 2, -3]] # Calculates the maximum # possible product calculateProduct(arr, 0, 1) # Print the maximum product print(maximum) |
C#
// C# program for the // above approach using System; public class GFG{ static int maximum = -int.MaxValue; // Function to find maximum product // possible by taking exactly one element // from each array of the list static void calculateProduct(int[,] list, int index, int product) { // If last index is encountered if (index + 1 == list.GetLength(0)) { foreach(int i in GetRow(list,index)) { // Find the maximum product maximum = Math.Max(maximum, product * i); } // Otherwise, recursively calculate // maximum product for every element } else { foreach(int i in GetRow(list,index)) calculateProduct(list, index + 1, product * i); } } public static int[] GetRow(int[,] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int[rowLength]; for (var i = 0; i < rowLength; i++) { rowVector[i] = matrix[row, i]; } return rowVector; } // Driver Code public static void Main(String[] args) { // Given list of N arrays int[,] arr = { { -3, -4,0 }, { 1, 2, -3 } }; // Calculates the maximum // possible product calculateProduct(arr, 0, 1); // Print the maximum product Console.Write(maximum); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Stores the maximum product var maximum = -1000000000; // Function to find maximum product // possible by taking exactly one element // from each array of the list function calculateProduct(List, index, product) { // If last index is encountered if(index + 1 == List.length) { for(var i =0; i< List[index].length; i++) { // Find the maximum product maximum = Math.max (maximum, product *List[index][i]); } // Otherwise, recursively calculate // maximum product for every element } else { for(var i =0; i< List[index].length; i++) calculateProduct(List, index + 1, product * List[index][i]); } } // Driver Code // Count of given arrays var N = 2; // Given list of N arrays var arr = [[-3, -4], [1, 2, -3]]; // Calculates the maximum // possible product calculateProduct(arr, 0, 1); // Print the maximum product document.write( maximum); </script> |
Output:
12
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to consider the lowest negative (if any) and highest positive (if any) numbers from each array to maximize the product. Follow the steps below to solve the problem:
- Traverse the list of arrays arr[].
- For every array in the list, say arr[index], find the maximum and minimum elements present in it.
- If the last index has been reached, return the maximum and minimum obtained as a pair.
- If the maximum value obtained is negative, set it to None. If the minimum value obtained is positive, set it to None
- Otherwise:
- Recursively call to (index + 1), i.e., calculateProduct(list, index + 1) and store the result in [positive, negative].
- Find all combinations of maximum, minimum obtained in Step 1 with positive, negative found in step 3.1.
- Return the maximum positive and minimum negative formed among all the combinations.
- After completing the above steps, print the maximum product formed.
Below is the implementation of the above approach:
C++14
// CPP program for the above approach #include<bits/stdc++.h> using namespace std; // Function to return the product of 2 numbers int findProduct(int number_1, int number_2) { // If any of the two numbers is None if(number_1 == INT_MIN or number_2 == INT_MIN) return 0; // Otherwise, return the product else return number_1 * number_2; } // Function to calculate maximum product // by taking only one element from each // array present in the list pair<int,int> calculateProduct(vector<vector<int>> List, int index) { // Find the maximum and minimum // present in the current array int highest = *max_element(List[index].begin(),List[index].end()); int lowest = *min_element(List[index].begin(),List[index].end()); // If last index is reached, then // return the highest(positive) // and lowest(negative) values if(index + 1 == List.size()){ if(lowest < 0 and highest >= 0) return {highest, lowest}; else if(lowest <= 0 and highest <= 0) return {INT_MIN, lowest}; else if(lowest >= 0 and highest >= 0) return {highest, INT_MIN}; } // Store the positive and negative products // returned by calculating for the // remaining arrays pair<int,int> temp = calculateProduct(List, index + 1); int positive = temp.first; int negative = temp.second; // Calculate for all combinations of // highest, lowest with positive, negative // Store highest positive product int highPos = findProduct(highest, positive); // Store product of highest with negative int highNeg = findProduct(highest, negative); // Store product of lowest with positive int lowPos = findProduct(lowest, positive); // Store lowest negative product int lowNeg = findProduct(lowest, negative); // Return the maximum positive and // minimum negative product if(lowest < 0 and highest >= 0) return {max(highPos, lowNeg), min(highNeg, lowPos)}; else if(lowest <= 0 and highest <= 0) return {lowNeg, lowPos}; else if(lowest >= 0 and highest >= 0) return {max(lowPos, highPos), min(lowNeg, highNeg)}; } // Driver Code int main() { // Count of given arrays int N = 2; // Given list of N arrays vector<vector<int>>arr{{-3, -4}, {1, 2, -3}}; // Store the maximum positive and // minimum negative product possible pair<int,int> ans = calculateProduct(arr, 0); // Print the maximum product cout<<ans.first<<endl; } // This code is contributed by SURENDRA_GANGWAR. |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to return the product of 2 numbers static int findProduct(int number_1, int number_2) { // If any of the two numbers is None if(number_1 == Integer.MIN_VALUE || number_2 == Integer.MIN_VALUE) { return 0; } // Otherwise, return the product else return number_1 * number_2; } // Function to calculate maximum product // by taking only one element from each // array present in the list static ArrayList<Integer> calculateProduct(ArrayList<ArrayList<Integer>> List, int index) { // Find the maximum and minimum // present in the current array int highest = Collections.max(List.get(index)); int lowest = Collections.min(List.get(index)); // If last index is reached, then // return the highest(positive) // and lowest(negative) values if(index + 1 == List.size()) { if(lowest < 0 && highest >= 0) { return (new ArrayList<Integer>(Arrays.asList(highest, lowest))); } else if(lowest <= 0 && highest <= 0) { return (new ArrayList<Integer>(Arrays.asList(Integer.MIN_VALUE, lowest))); } else if(lowest >= 0 && highest >= 0) { return (new ArrayList<Integer>(Arrays.asList(highest,Integer.MIN_VALUE))); } } // Store the positive and negative products // returned by calculating for the // remaining arrays ArrayList<Integer> temp = calculateProduct(List, index + 1); int positive = temp.get(0); int negative = temp.get(1); // Calculate for all combinations of // highest, lowest with positive, negative // Store highest positive product int highPos = findProduct(highest, positive); // Store product of highest with negative int highNeg = findProduct(highest, negative); // Store product of lowest with positive int lowPos = findProduct(lowest, positive); // Store lowest negative product int lowNeg = findProduct(lowest, negative); // Return the maximum positive and // minimum negative product if(lowest < 0 && highest >= 0) { return (new ArrayList<Integer>(Arrays.asList(Math.max(highPos, lowNeg), Math.min(highNeg, lowPos)))); } else if(lowest <= 0 && highest <= 0) { return (new ArrayList<Integer>(Arrays.asList(lowNeg, lowPos))); } else if(lowest >= 0 && highest >= 0) { return (new ArrayList<Integer>(Arrays.asList(Math.max(lowPos, highPos), Math.min(lowNeg, highNeg)))); } return (new ArrayList<Integer>(Arrays.asList(0,0))); } // Driver Code public static void main (String[] args) { // Count of given arrays int N = 2; // Given list of N arrays ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>(); arr.add(new ArrayList<Integer>(Arrays.asList(-3, -4))); arr.add(new ArrayList<Integer>(Arrays.asList(1, 2, -3))); // Store the maximum positive and // minimum negative product possible ArrayList<Integer> ans = calculateProduct(arr, 0); // Print the maximum product System.out.println(ans.get(0)); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python program for the above approach # Function to return the product of 2 numbers def findProduct(number_1, number_2): # If any of the two numbers is None if(number_1 == None or number_2 == None): return 0 # Otherwise, return the product else: return number_1 * number_2 # Function to calculate maximum product # by taking only one element from each # array present in the list def calculateProduct(List, index): # Find the maximum and minimum # present in the current array highest = max(List[index]) lowest = min(List[index]) # If last index is reached, then # return the highest(positive) # and lowest(negative) values if(index + 1 == len(List)): if(lowest < 0 and highest >= 0): return [highest, lowest] elif(lowest <= 0 and highest <= 0): return [None, lowest] elif(lowest >= 0 and highest >= 0): return [highest, None] # Store the positive and negative products # returned by calculating for the # remaining arrays [positive, negative] = calculateProduct(List, index + 1) # Calculate for all combinations of # highest, lowest with positive, negative # Store highest positive product highPos = findProduct(highest, positive) # Store product of highest with negative highNeg = findProduct(highest, negative) # Store product of lowest with positive lowPos = findProduct(lowest, positive) # Store lowest negative product lowNeg = findProduct(lowest, negative) # Return the maximum positive and # minimum negative product if(lowest < 0 and highest >= 0): return [max(highPos, lowNeg), min(highNeg, lowPos)] elif(lowest <= 0 and highest <= 0): return [lowNeg, lowPos] elif(lowest >= 0 and highest >= 0): return [max(lowPos, highPos), min(lowNeg, highNeg)] # Driver Code # Count of given arrays N = 2 # Given list of N arrays arr = [[-3, -4], [1, 2, -3]] # Store the maximum positive and # minimum negative product possible positive, negative = calculateProduct(arr, 0) # Print the maximum product print(positive) |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Linq; public class GFG { // Function to return the product of 2 numbers static int findProduct(int number_1, int number_2) { // If any of the two numbers is None if(number_1 == Int32.MinValue || number_2 == Int32.MinValue) { return 0; } // Otherwise, return the product else return number_1 * number_2; } // Function to calculate maximum product // by taking only one element from each // array present in the list static List<int> calculateProduct(List<List<int>> List, int index) { // Find the maximum and minimum // present in the current array int highest = List[index].Max(); int lowest = List[index].Min(); // If last index is reached, then // return the highest(positive) // and lowest(negative) values if(index + 1 == List.Count) { if(lowest < 0 && highest >= 0) { return (new List<int>(){highest,lowest}); } else if(lowest <= 0 && highest <= 0) { return (new List<int>(){Int32.MinValue, lowest}); } else if(lowest >= 0 && highest >= 0) { return (new List<int>(){highest, Int32.MinValue}); } } // Store the positive and negative products // returned by calculating for the // remaining arrays List<int> temp = calculateProduct(List, index + 1); int positive = temp[0]; int negative = temp[1]; // Calculate for all combinations of // highest, lowest with positive, negative // Store highest positive product int highPos = findProduct(highest, positive); // Store product of highest with negative int highNeg = findProduct(highest, negative); // Store product of lowest with positive int lowPos = findProduct(lowest, positive); // Store lowest negative product int lowNeg = findProduct(lowest, negative); // Return the maximum positive and // minimum negative product if(lowest < 0 && highest >= 0) { return (new List<int>(){Math.Max(highPos, lowNeg), Math.Min(highNeg, lowPos)}); } else if(lowest <= 0 && highest <= 0) { return (new List<int>(){lowNeg, lowPos}); } else if(lowest >= 0 && highest >= 0) { return (new List<int>(){Math.Max(lowPos, highPos), Math.Min(lowNeg, highNeg)}); } return (new List<int>(){0,0}); } // Driver Code static public void Main () { // Given list of N arrays List<List<int>> arr = new List<List<int>>(); arr.Add(new List<int>(){-3, -4}); arr.Add(new List<int>(){1, 2, -3}); // Store the maximum positive and // minimum negative product possible List<int> ans = calculateProduct(arr, 0); // Print the maximum product Console.WriteLine(ans[0]); } } // This code is contributed by rag2127. |
Javascript
<script> // JavaScript program for the above approach // Function to return the product of 2 numbers function findProduct(number_1,number_2) { // If any of the two numbers is None if(number_1 == Number.MIN_VALUE || number_2 == Number.MIN_VALUE) { return 0; } // Otherwise, return the product else return number_1 * number_2; } // Function to calculate maximum product // by taking only one element from each // array present in the list function calculateProduct(List,index) { // Find the maximum and minimum // present in the current array let highest = Math.max(...List[index]); let lowest = Math.min(...List[index]); // If last index is reached, then // return the highest(positive) // and lowest(negative) values if(index + 1 == List.length) { if(lowest < 0 && highest >= 0) { return ([highest, lowest]); } else if(lowest <= 0 && highest <= 0) { return ([Number.MIN_VALUE, lowest]); } else if(lowest >= 0 && highest >= 0) { return ([highest,Number.MIN_VALUE]); } } // Store the positive and negative products // returned by calculating for the // remaining arrays let temp = calculateProduct(List, index + 1); let positive = temp[0]; let negative = temp[1]; // Calculate for all combinations of // highest, lowest with positive, negative // Store highest positive product let highPos = findProduct(highest, positive); // Store product of highest with negative let highNeg = findProduct(highest, negative); // Store product of lowest with positive let lowPos = findProduct(lowest, positive); // Store lowest negative product let lowNeg = findProduct(lowest, negative); // Return the maximum positive and // minimum negative product if(lowest < 0 && highest >= 0) { return ([(Math.max(highPos, lowNeg)), Math.min(highNeg, lowPos)]); } else if(lowest <= 0 && highest <= 0) { return ([lowNeg, lowPos]); } else if(lowest >= 0 && highest >= 0) { return ([(Math.max(lowPos, highPos)), Math.min(lowNeg, highNeg)]); } return ([0,0]); } // Driver Code // Count of given arrays let N = 2; // Given list of N arrays let arr = [[-3, -4],[1, 2, -3]]; // Store the maximum positive and // minimum negative product possible let ans = calculateProduct(arr, 0); // Print the maximum product document.write(ans[0]); // This code is contributed by patel2127 </script> |
Output:
12
Time Complexity: O(N*length(array))
Auxiliary Space: O(1)
