Design: Prelude to reductions. In the maximum subarray problem you are

given an array A$[1..$n$]$ of values $($some of which may be negative$),$ and your task

is to find a non$-$empty subinterval A$[$i$..$j$]$ where the sum of values is maximum. In

the maximum ordered difference problem you are given an array B$[1..$n$]$ of values,

and your task is to find a subinterval B$[$i$..$j$]$ of length at least two with maximum

B$[$j$]$ B$[$i$].$ Show that these problems are asymptotically equivalent: If you can

solve one in linear time, you can solve the other in linear time. $($That is$,$ form a

linear$-$time reduction from one problem to the other, and back. We will later see

many more examples of this technique.$)$ Hint. Think about cumulative sums and

differences between consecutive values.