TAOCP 1.2.10 Exercise 20
Let M=\max_{1\le k\le n}|a_k-b_k|.
Section 1.2.10: Analysis of an Algorithm
Exercise 20. [M22] Suppose we want to calculate $\max{|a_1-b_1|,|a_2-b_2|,\ldots,|a_n-b_n|}$ when $b_1 \le b_2 \le \cdots \le b_n$. Show that it is sufficient to calculate $\max{m_L,m_R}$, where
$$ m_L = \max{a_k-b_k \mid a_k \text{ is a left-to-right maximum of } a_1a_2\ldots a_n}, $$
$$ m_R = \max{b_k-a_k \mid a_k \text{ is a right-to-left minimum of } a_1a_2\ldots a_n}. $$
Verified: yes
Solve time: 59s
Solution
Let
$$ M=\max_{1\le k\le n}|a_k-b_k|. $$
Define
$$ m_L=\max{a_k-b_k\mid a_k \text{ is a left-to-right maximum}}, $$
$$ m_R=\max{b_k-a_k\mid a_k \text{ is a right-to-left minimum}}. $$
We shall prove that
$$ M=\max{m_L,m_R}. $$
Since every quantity occurring in the definitions of $m_L$ and $m_R$ is one of the numbers $|a_k-b_k|$, it is immediate that
$$ m_L\le M,\qquad m_R\le M, $$
hence
$$ \max{m_L,m_R}\le M. \tag{1} $$
It remains to prove the reverse inequality.
Consider an arbitrary index $k$.
First suppose that $a_k\ge b_k$. We shall show that
$$ a_k-b_k\le m_L. $$
If $a_k$ is a left-to-right maximum, this is true by definition of $m_L$.
Otherwise there exists some $j<k$ with
$$ a_j>a_k. $$
Since
$$ b_1\le b_2\le\cdots\le b_n, $$
we have
$$ b_j\le b_k. $$
Therefore
$$ a_j-b_j\ge a_j-b_k>a_k-b_k. $$
If $a_j$ is not a left-to-right maximum, the same argument may be applied to $j$. Repeating finitely many times, we eventually reach an index $i\le k$ such that $a_i$ is a left-to-right maximum and
$$ a_i-b_i>a_k-b_k. $$
Hence
$$ a_k-b_k\le m_L. \tag{2} $$
Next suppose that $a_k\le b_k$. We shall show that
$$ b_k-a_k\le m_R. $$
If $a_k$ is a right-to-left minimum, this is true by definition of $m_R$.
Otherwise there exists some $j>k$ with
$$ a_j<a_k. $$
Since the sequence $b_1,b_2,\ldots,b_n$ is nondecreasing,
$$ b_j\ge b_k. $$
Therefore
$$ b_j-a_j\ge b_k-a_j>b_k-a_k. $$
If $a_j$ is not a right-to-left minimum, the same argument may be applied to $j$. Repeating finitely many times, we eventually reach an index $i\ge k$ such that $a_i$ is a right-to-left minimum and
$$ b_i-a_i>b_k-a_k. $$
Hence
$$ b_k-a_k\le m_R. \tag{3} $$
From (2) and (3), every index $k$ satisfies
$$ |a_k-b_k| = \begin{cases} a_k-b_k \le m_L, & a_k\ge b_k,\[4pt] b_k-a_k \le m_R, & a_k\le b_k. \end{cases} $$
Thus
$$ |a_k-b_k|\le \max{m_L,m_R} $$
for all $k$. Taking the maximum over all $k$ gives
$$ M\le \max{m_L,m_R}. \tag{4} $$
Combining (1) and (4), we obtain
$$ M=\max{m_L,m_R}. $$
Therefore it is sufficient to calculate $m_L$ and $m_R$ instead of examining all values $|a_k-b_k|$.
This completes the proof.
∎