0
$\begingroup$

Let's say we have an array $a_1,\ldots,a_n$ and a new array $b_i = a_{i+1} - a_i$ for $1 \leq i \leq n-1$.

Hence $$ \max_{\substack{i < j \\ a_i < a_j}} |a_j-a_i| = \max_{i<j} (a_j-a_i) = \max_{i<j} b_i + \cdots + b_{j-1}. $$

To understand the last equality one have to note that $a_j - a_i = b_i + \cdots + b_{j-1}.$ But I don't get it. I'm only able to get:

\begin{align} a_j - a_i &= - b_j + a_{j+1} + b_i - a_{i+1} \\ \end{align}

This is important to understand an algorithm that finds the difference between the adjacent elements of the array to find the maximum difference.

$\endgroup$
1
$\begingroup$

$b_i+b_{i+1}+\cdots +b_{j-1}=(a_{i+1}-a_i)+(a_{i+2}-a_{i+1})+\cdots+ (a_{j}-a_{j-1})$. This is a telescopic sum. All terms cancel out except $a_j-a_i$.

$\endgroup$
  • $\begingroup$ Thanks ! How can I figure that out from $\max_{i<j}(a_j-a_i)$ ? $\endgroup$ – ThePassenger Apr 3 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.