See the original problem on HackerRank.
You are given a sequence of integers S
, your task is to find a pair i,j
of indices with i<j
that maximizes the difference S[j]S[i]
.
Note that what makes this challenge more interesting is the requirement of order, that i < j (without it you simply need to find the maximum and minimum element of S).
You have to output the value of the maximum difference.
Input Format
An integer N
followed by N
space separated integers S[i]
on a new line.
Constraints
1<N<=10^6
0<=S[i]<=10^4
Output Format
The maximum difference as an integer.
Solutions
This problem has a naive quadratic solution that involves considering every pairs \(i,j\) with \(j>i\) and tracking the maximum. What makes this naive is that it is a bruce force solution that does not consider the input domain or the structure of the problem.
To see the solution, consider what pairs we should consider for the index \(j\). Let’s suppose that \(j\) is the right hand index so we need only look at elements of \(S\) that precede \(j\). The difference \(s[j]s[i]\) is maximized for the index \(i\) that contains the minimum element of \(s[1],…s[j1]\).
Therefore, instead of looking over pairs, we need only to keep track of the maximum element preceding any other index. This is linear.
Here is a possible C++ implementation of the described idea:


Another interesting solution  less efficent  based on prefix sum and zip  map  reduce:


Just for fun, an alternative solution is based on the Maximum Subarray Sum problem. We first calculate the differences between adjacent elements and then solve the maximum subarray problem on the resulting array.
In C++ we can combine several standard algorithms:

