Computing elements that result in maximum product efficiently →
In a previous post we were wondering if we can compute the elements (from a given unsorted array of integers) that result in maximum product faster than O(n logn). It turns out we can do a linear scan of the array, keeping track of the largest two and the smallest two elements. One of these pairs would result in the maximum product.
void maxprod(std::vector<int> arr)
{
int n = arr.size();
int max1 = arr[0], max2 = INT_MIN;
int min1 = arr[0], min2 = INT_MAX;
for (int i = 1; i < n; i++)
{
if (arr[i] > max1)
{
max2 = max1;
max1 = arr[i];
}
else if (arr[i] > max2)
max2 = arr[i];
if (arr[i] < min1)
{
min2 = min1;
min1 = arr[i];
}
else if (arr[i] < min2)
min2 = arr[i];
}
if (max1 * max2 > min1 * min2)
std::cout << max1 << ", " << max2 << std::endl;
else
std::cout << min1 << ", " << min2 << std::endl;
}
The algorithm is very straight-forward that the code itself is self explanatory.