ronith
6/16/2018 - 6:23 AM

Find a pair with maximum product in array of Integers

Given an array with both +ive and -ive integers, return a pair with highest product.

Examples :

Input: arr[] = {1, 4, 3, 6, 7, 0}
Output: {6,7}

Input: arr[] = {-1, -3, -4, 2, 0, -5} Output: {-4,-5}

An Efficient Solution can solve the above problem in single traversal of input array. The idea is to traverse the input array and keep track of following four values. a) Maximum positive value b) Second maximum positive value c) Maximum negative value i.e., a negative value with maximum absolute value d) Second maximum negative value.

Find a pair with maximum product in array of Integers.cpp
content_copyfile_download
// https://www.geeksforgeeks.org/return-a-pair-with-maximum-product-in-array-of-integers/
#include <iostream>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n];
    for (int i=0;i<n;i++)
        cin>>a[i];

    int min1=INT_MAX, min2=INT_MAX, max1=INT_MIN, max2=INT_MIN;

    for (int i=0;i<n;i++){
        if (a[i] > max1){
            max2=max1;
            max1=a[i];
        }
        else if (a[i] > max2 && a[i] < max1){
            max2=a[i];
        }
        if (a[i] < min1){
            min2=min1;
            min1=a[i];
        }
        else if (a[i] > min1 && a[i] < min2){
            min2=a[i];
        }
    }
    if (min1*min2 < max1*max2)
        cout << "Max product is: " << max1*max2 << ", {"<<max2 << ", " << max1 << "}";
    else
        cout << "Max product is: " << min1*min2 << ", {"<<min1 << ", " << min2 << "}";
}