702869. Pair with greatest product in array
Easy
Pair with greatest product in array
Summary
Given an array of integers, find the pair of elements that has the greatest product. This problem involves arrays and data structures.
Detailed Explanation
The brute force approach to solve this problem is to generate all possible pairs of elements from the array and then calculate their products. We can keep track of the maximum product seen so far and return it at the end.
Here's a step-by-step breakdown of the solution:
- Initialize a variable
max_productto store the maximum product seen so far. - Iterate over all possible pairs of elements from the array.
- For each pair, calculate their product and compare it with
max_product. - If the new product is greater than
max_product, updatemax_productwith the new value. - After iterating over all pairs, return the maximum product found.
The time complexity of this approach is O(n^2) where n is the size of the array, as we are generating all possible pairs and calculating their products. The space complexity is O(1), as we only need a few extra variables to store the maximum product and the current pair being processed.
Optimized Solutions
Java
public class Main {
public static int findGreatestProduct(int[] arr) {
int max_product = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
int product = arr[i] * arr[j];
if (product > max_product) {
max_product = product;
}
}
}
return max_product;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
System.out.println(findGreatestProduct(arr));
}
}