Given an unsorted array A $=\{$ai$\}$

n

i$=1$ of size n$,$ provide an algorithm that finds

r $=$ max $|$ai $$ aj $|$

i$,$j$<=$n

using at most O$($n$)$ comparisons on the worst case input. Bonus: design an algorithm which uses at most $3$

$2$

n comparisons on the worst case input. Prove that your

algorithm is correct.