Maximum Product Pair - C++ Solution

1. Introduction

The "Maximum Product Pair" problem is an interesting array-based challenge that tests a programmer's ability to identify patterns and optimize solutions. It involves finding two numbers in an array whose product is the maximum among all pairs.

Problem

Given an integer array, the task is to find a pair of elements that has the maximum product. The solution should consider various scenarios, including negative numbers, and return a pair that yields the highest product. If the array does not have enough elements to form a pair, the function should return (-1, -1).

2. Solution Steps

1. Handle edge cases where the array size is less than 2.

2. Initialize variables to keep track of the highest and second-highest values, and also the lowest and second-lowest values.

3. Traverse the array to find these values.

4. Compare the product of the two highest values with the product of the two lowest values (as two negative numbers can give a positive product).

5. Return the pair that gives the higher product.

3. Code Program

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

// Function to find a pair with the maximum product in an array
pair<int, int> findMaxProductPair(const vector<int>& nums) {
    if (nums.size() < 2) {
        return {-1, -1}; // Not enough elements to form a pair
    }

    // Initialize maximum and minimum values
    int max1 = numeric_limits<int>::min(), max2 = max1;
    int min1 = numeric_limits<int>::max(), min2 = min1;

    for (int num : nums) {
        // Update maximum values
        if (num > max1) {
            max2 = max1;
            max1 = num;
        } else if (num > max2) {
            max2 = num;
        }

        // Update minimum values
        if (num < min1) {
            min2 = min1;
            min1 = num;
        } else if (num < min2) {
            min2 = num;
        }
    }

    // Compare products of max and min values
    if (max1 * max2 > min1 * min2) {
        return {max1, max2};
    } else {
        return {min1, min2};
    }
}

int main() {
    vector<int> nums = {-10, -3, 5, 6, -2};
    auto result = findMaxProductPair(nums);
    cout << "(" << result.first << ", " << result.second << ")" << endl;
    return 0;
}

Output:

(-10, -3)

Explanation:

The function findMaxProductPair first checks if the input array has enough elements to form a pair. 

It then traverses the array to find the highest and second-highest numbers, as well as the lowest and second-lowest numbers. 

This is important as a high product can be achieved by multiplying two large positive numbers or two large negative numbers. The function finally returns the pair that yields the maximum product. 

This approach ensures that all scenarios are considered, including cases with negative numbers, providing an optimal and efficient solution.


Comments