Problem Statement
We have given an integer array and we need to find two numbers from the array whose product is the maximum. In other words, we need to find the maximum product of two integers in the given array.
Example Input
arr = [10, 10, 3, 4, 2, 25]
Output
output = [10, 10] or [25,4]
Explanation
In the above array, we have 6 elements. Out of those 6 elements, two pairs
(10, 10)
and
(25, 4)
have the maximum product value, i.e.,
100
.
Approach 1
Naive Algorithm
In the Naive algorithm, we will go for the brute force technique, where we will multiply every subarray pair present in the array. We will look for the maximum product value pair and print it.
Algorithm

Initialize a
max_product
with a minimal initial value. 
Also, initialize two variables
val1
andval2
that will represent two elements with the maximum product.  Create a nested for loop for every pair present in the array.

Inside the nested loop, check for the maximum product, and store the element values in the
val1
andval2
and updatemax_product
value.

C++ Program
#include <iostream>
using namespace std;
// function to find the maximum product pair
//using naive approach
void find_maximum_product(int arr[], int n)
{
// initialize a max product variable
// with a minimal value
int max_product = 999999999;
int val1, val2;
// find out every pair present in the array
for (int i = 0; i < n  1; i++)
{
for (int j = i + 1; j < n; j++)
{
//check for the max product pairs
if (max_product < arr[i] * arr[j])
{
//update max_product value
max_product = arr[i] * arr[j];
val1 = arr[i];
val2 = arr[j];
}
}
}
cout<<"Max Product Pair is ("<<val1 <<", "<<val2<<")";
int main()
{
//given array
int arr[] = { 10, 10, 3, 4, 2, 25 };
//length of the array
int n = sizeof(arr) / sizeof(arr[0]);
find_maximum_product(arr, n);
return 0;
}
Output

Python Program
#function to find the maximum product pair
# using naive approach
def find_maximum_product(arr, n):
# initialize a max product variable
max_product = 999999999
#find out every pair present in the array
for i in range(n):
for j in range(i+1, n):
# check for the max product pairs
if max_product < arr[i]* arr[j]:
#update max_product value
max_product = arr[i]*arr[j]
val1 = arr[i]
val2 = arr[j]
print(f"Max Product Pair is ({val1}, {val2})")
if __name__=="__main__":
#given array
arr= [10, 10, 3, 4, 2, 25 ]
#len of array
n = len(arr)
find_maximum_product(arr,n)
Output
Complexity Analysis
Time Complexity: The time complexity of the above algorithm is O(N^2) where N is the total number of elements present in the array.
Space Complexity: O(1) , because we did not use any extra space.
Approach 2
Sort the Array and Product the Largest and Secondlargest Pair
The idea behind this approach is very straightforward. First, we have to sort the array using quicksort or an optimized sorting algorithm. After that, we need to check the product of the last and second last elements and first and second elements (in case of negative values). Finally, we need to print the pair whose product value is higher.
Algorithm
 Sort the array.
 Find the product of the first two elements.
 Find the product of the last two elements.
 Check if the product of the first two elements is greater than the last two elements, and print the pair with the maximum product value.

C++ Program
#include
#include
using namespace std;
// function to find the maximum product pair
//using naive approch
void find_maximum_product(int arr[], int n)
{ //sort the array
sort(arr, arr + n);
// first 2 elements
int min1 = arr[0];
int min2 = arr[1];
// last 2 elements
int max1= arr[n1];
int max2 = arr[n2];
if((min1*min2)>= (max1*max2))
cout<<"Max Product Pair is ("<<min1 <<", "<<min2<<")";
else
cout<<"Max Product Pair is ("<<max1 <<", "<<max2<<")";
}
int main()
{
//given array
int arr[] = { 10, 10, 3, 4, 2, 25 };
//length of the array
int n = sizeof(arr) / sizeof(arr[0]);
find_maximum_product(arr, n);
return 0;
}
Output

Python Program
#function to find the maximum product pair
# using sorting approch
def find_maximum_product(arr, n):
arr.sort()
#first 2 elements
min1, min2 = arr[0], arr[1]
# last 2 elements
max1, max2 = arr[n1], arr[n2]
if (min1*min2) >= (max1*max2):
print(f"Max Product Pair is ({min1}, {min2})")
else:
print(f"Max Product Pair is ({max1}, {max2})")
if __name__=="__main__":
#given array
arr= [10, 10, 3, 4, 2, 25 ]
#length of array
n = len(arr)
find_maximum_product(arr,n)
Output
Complexity Analysis
Time Complexity: The time complexity of the above program is O(Nlog(N)) because of sorting.
Space Complexity: The space complexity is O(1) because we did not use any extra array or space to store array values.
Approach 3
Optimize Algorithm with Linear Time Complexity
In the previous approach, we picked the minimum and second minimum, and maximum and second maximum elements by sorting the array. If we only need 4 elements from the array, we do not need to sort the array as we can find those 4 elements using a single traversal or loop. In this optimize algorithm, we will use logic to find out the maximum, second maximum, minimum, and second minimum elements from the array. Finally, we will figure out which pair has the largest product value.
Algorithm

Set maximum and second maximum initial values by
array[0]
and 999999999 (smallest value). 
Set minimum and second minimum initial values by
array[0]
and 999999999 (largest value).  Create a loop that will traverse through the complete array.
 Inside the loop, check if the element is greater than the maximum value, and then update the maximum value and set the second maximum by maximum.
 Also, check if the array element is smaller than the maximum value but greater than the second maximum value. In that case, only update the second maximum value by the array element.
 Repeat steps 4 and 5 to find the minimum values.
 At last, check whether the product of the minimum and second minimum values is greater than the maximum and second maximum values.

C++ Program
#include
#include
using namespace std;
// function to find the maximum product pair
//using naive approch
void find_maximum_product(int arr[],int n)
{ //initialize maximum and second maximum values
int max1 = arr[0];
int max2 = 999999999999; //as small as possible
// initialize minimum and second minimum values
int min1 = arr[0];
int min2 = 9999999999; //as large as possible
for(int i=1; i<n; i++)
{
// check if the current element is greater than maximum value
if(arr[i]>max1)
{
//update the maximum and second maximum values
max2 = max1;
max1= arr[i];
}
//check if the current element is greater than
//second maximum number but smaller than maximum number
//only update second maximum number
else if(arr[i]> max2)
{
max2 = arr[i];
}
// check if the current element is smaller than maximum value
if(arr[i]<min1)
{
//update the minimum and second minimum values
min2 = min1;
min1= arr[i];
}
//check if the current element is smaller than
//second minimum number but greater than minimum number
//only update second minimum number
else if(arr[i]< min2)
{
min2 = arr[i];
}
}
if((min1*min2)>= (max1*max2))
cout<<"Max Product Pair is ("<<min1 <<", "<<min2<<")";
else
cout<<"Max Product Pair is ("<<max1 <<", "<<max2<<")";
}
int main()
{
//given array
int arr[] = { 10, 10, 3, 4, 2, 25 };
//length of the array
int n = sizeof(arr) / sizeof(arr[0]);
find_maximum_product(arr, n);
return 0;
}
Output

Python Program
#function to find the maximum product pair
# using sorting approch
def find_maximum_product(arr, n):
# initialize maximum and second maximum values
max1, max2 = arr[0], 999999999999
#initialize minimum and second minimum values
min1, min2 = arr[0], 99999999999
for i in range(1, n):
# check if the current element is greater than maximum value
if arr[i]> max1:
# update the maximum and second maximum values
max2 = max1
max1 = arr[i]
# check if the current element is greater than
# second maximum number but smaller than maximum number
# only update second maximum number
elif arr[i]>max2:
max2 = arr[i]
# check if the current element is smaller than maximum value
if arr[i]= (max1*max2):
print(f"Max Product Pair is ({min1}, {min2})")
else:
print(f"Max Product Pair is ({max1}, {max2})")
if __name__=="__main__":
#given array
arr= [10, 10, 3, 4, 2, 25 ]
#length of array
n = len(arr)
find_maximum_product(arr,n)
Output
Complexity Analysis
 Time Complexity: O(N) , where N is the total number of elements present in the array.
 Space Complexity: O(1) , because we did not use any extra space to store array elements.
Wrapping Up
In this tutorial, we learned three different algorithms to find the maximum product of two integers in an array. Also, we implemented all three algorithms using C++ and Python programming languages.
The first approach uses the Brute force technique where we calculated the product of every possible pair to find the pair with the maximum product value. The time complexity of this approach is O(N^2).
In the second approach, we optimized the algorithm to find the pair with the maximum product value by sorting the array. Also, this approach has O(Nlog(N)) time complexity.
We optimized the solution and solved the problem with the linear time complexity of O(N) in the third approach.
People are also reading:
 Construct a Binary Tree from Inorder and Preorder traversals
 Construct a tree from Inorder and Level order traversals
 Write a Program to read from a text file and then write in another text file
 Write a C++ Program to print a Man using Graphics
 Python Array
 Write a Program to convert given inches into equivalent yard, and feet
 Program to Find LCM and HCF of two numbers
 Sort an array in one swap whose two elements are swapped
 Move all zeros present in an array to the end
 Longest Palindromic Subsequence using Dynamic Programming
 Rod Cutting Problem – Dynamic Programming
Leave a Comment on this Post