Fast Solution: Maximum Pairwise Product

Fast algorithm

In search of a faster algorithm, we play with small examples like $[5,6,2,7,4]$. Eureka—it suffices to multiply the two largest elements of the array: $7$ and $6$! Since we need to find the largest and the second-largest elements, we need only two scans of the sequence. During the first scan, we find the largest element. During the second scan, we find the largest element among the remaining ones by skipping the element found at the previous scan.

---

 $MaxPairwiseProductFast(A[1 . . . n])$:
  $index_1 \leftarrow 1$
  for $i$ from $2$ to $n$:
       if $A[i] > A[index_1]$:
             $index_1 \leftarrow i$
  $index_2 \leftarrow 1$
  for $i$ from $2$ to $n$:
       if $A[i] \neq A[index_1]$ and $A[i] > A[index_2]$:
             $index_2 \leftarrow i$
  return $A[index_1] \cdot A[index_2]$

---