Write a Java program to find maximum product of two integers in a given array of integers

In the previous article, we have seen Java Program to Find the Index of an Element Before Which All elements are Greater and After Which All Elements are Smaller

Table of Contents Show

Method-1: Java Program to Find Maximum Product of Two Integers in an Array By Using Sorting Technique
Method-2: Java Program to Find Maximum Product of Two Integers in an Array By Finding First Two Biggest Element
Approach 1
Naive Algorithm
Complexity Analysis
Algorithm
Complexity Analysis
Approach 3
Optimize Algorithm with Linear Time Complexity
Algorithm
Complexity Analysis
Wrapping Up

In this article we are going to see how we can find maximum product of two integers in an array.

As we have to write a program which will find the maximum product of two integers in an array of integers so our first target should be finding first two biggest numbers from the array elements. As it is very much clear that product of two bigger number will give maximum result than product of two smaller numbers.

For example:

If we have an array say arr=[1, 7, 4, 2, 8, 6, 3, 9, 5] Then in this array first two bigger numbers are 9 and 8. So product is 9*8=72 which is maximum product we can find than any other possible combinations of array elements.

Let’s see different ways to find maximum product of two integers in an array.

By Using Sorting Technique
By Finding First Two Biggest Element

Method-1: Java Program to Find Maximum Product of Two Integers in an Array By Using Sorting Technique

Approach:

Declare an array and with array elements.
Sort the array by using Arrays.sort() method.
Now array is sorted in ascending order.
So, find the product of last element and second last element which will give the maximum product value.
Print the result.

Program:

import java.util.Arrays; import java.util.Comparator; class Main { public static void main(String[] args) { //integer array declared along with integer elements Integer[] input = { 1,6,3,4,5 }; // sort the array in ascending order Arrays.sort(input); //as array is sorted in ascending order //so last two elements are biggest elements //so by multiplying the last two elemnts we will get maximum product long result=input[input.length-1]*input[input.length-2]; //input[input.length-1] represents last elements //input[input.length-2] second last element System.out.println("Two numbers are "+ input[input.length-1] +" and "+ input[input.length-2]+" having maximum product "+result); } } Output: Two numbers are 6 and 5 having maximum product 30

Method-2: Java Program to Find Maximum Product of Two Integers in an Array By Finding First Two Biggest Element

Approach:

Take user input of length of array.
Take input of integer array elements.
Call the user defined method findBiggest() to find first 2 big elements in the array say firstNumber, secondNumber
After getting 2 big elements in the array, inside that findBiggest() method, call findMaxProduct() method.
Inside findMaxProduct() method multiply firstNumber and secondNumber which will give the maximum product value.
Print the result.

Program:

import java.util.Scanner; public class Main { public static void main(String args[]) { int length = 0; Scanner sc = new Scanner(System.in); System.out.println("Enter number of elements in array: "); //array length taken as input length = sc.nextInt(); //array declared int[] arr = new int[length]; //take input of single digited number as array element System.out.println("Enter elements into array: "); //taking input of array elements for (int i = 0; i < length; i++) { arr[i] = sc.nextInt(); } System.out.println("First 2 biggest numbers in array : "); //calling findBiggest() method findBiggest(arr); } //user defined method to find first 2 biggest element private static void findBiggest(int[] arr) { int firstNumber = arr[0]; int secondNumber = arr[1]; for (int i = 0; i < arr.length; i++) { if (arr[i] > firstNumber) { secondNumber = firstNumber; firstNumber = arr[i]; } else if (arr[i] > secondNumber) { secondNumber = arr[i]; } } System.out.println("First biggest number : " + firstNumber); System.out.println("Second biggest number : " + secondNumber); //calling findMaxProduct() method to find maximum product findMaxProduct(firstNumber,secondNumber); } public static void findMaxProduct(int firstNumber, int secondNumber) { //multiplying both numbers to find product value int result= firstNumber*secondNumber; System.out.println("Two numbers are "+ firstNumber +" and "+ secondNumber+" having maximum product "+result); } } Output: Enter number of elements in array: 5 Enter elements into array: 40 10 30 50 20 First 2 biggest numbers in array : First biggest number : 50 Second biggest number : 40 Two numbers are 50 and 40 having maximum product 2000

Provided list of Simple Java Programs is specially designed for freshers and beginners to get familiarize with the concepts of Java programming language and become pro in coding.

Related Java Programs:

You should change

if (arr[i]*arr[j] > arr[0]*arr[1])

if (arr[i]*arr[j] > a * b)

Since arr[0]*arr[1] is just the original max product, so you shouldn't be comparing against it.

Also note that your solution is not as efficient as it can be, since you are using a nested loop, which requires O(n^2) running time.

You can achieve linear (O(n)) running time if you use the fact that the max product is either the product of the two highest positive values or the product of the two lowest negative values. This means that if you find these 4 numbers, which can be done with a single loop, you'll find the max product.

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 and val2 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 and val2 and update max_product value.

#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

#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.

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.

#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[n-1]; int max2 = arr[n-2]; 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

#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[n-1], arr[n-2] 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.

#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

#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: