Given an array of student scores $s$ of length $n$, the question formally asks to maximize $s[i] - s[j]$ such that $i < j < n $. We done the maximum difference as $d_{max}$.

One naive approach could to generate all $(s[i],s[j])$ pairs such that $i < j$ and take the maximum out of them. This is an $\mathcal{O}(n^2)$ approach. Given that $n$ could be as high as $10^5$, this will definitely exceed time limit.

But we don’t really need to generate all pairs to find out the answer. We keep a variable called $\textrm{compare_value}$ or $\textrm{cv}$ in short. Initially we set $\textrm{cv}$ to index $s[0]$. There are two possibilities for the next index $i$:

  • $\textrm{cv} \geq s[i]$
    • In this case, we update the $d_{max}$. This requires little explanation. If the subsequent indices have equal or lower values than $\textrm{cv}$, then we take the maximum difference between $\textrm{cv}$ and these indices’ values.
  • $\textrm{cv} < s[i]$
    • In this case, we set $\textrm{cv}$ to $s[i]$. Why? Because we want the difference to be maximized. Take an index $j$ such that $ i < j < n $ and $s[j] < \textrm{cv}$. As $\textrm{cv} < s[i]$, we have $s[j] < s[i]$. Then the difference between $s[i]$ and $s[j]$ is greater than the difference between $\textrm{cv}$ and $s[j]$. Namely, \[ d_{s[i] - s[j]} > d_{\textrm{cv} - s[j]} \] So if we don’t update $\textrm{cv}$ to $s[i]$, then $d_{max}$ will not be updated correctly.

Here’s the implementation in C++:

Time Complexity: $\mathcal{O}(n)$