If $b_i = a_{i+1} - a_i$ why does $a_j - a_i = b_i + \cdots + b_{j-1}.$ for $1 \leq i \leq n-1$?

36 Views Asked by At

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.

1

There are 1 best solutions below

1
On BEST ANSWER

$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$.