求 $a_j-a_i$ 的最大值

给定一个整数数组 a[n]，求 $\max(a_j - a_i), 0\leq i<j<n$。要求时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

这道题若没有最后的空间复杂度时间复杂度的要求，很简单，两层循环就能解决了。

这个题看似要使用动态规划，但仔细一想，不好弄，不能使用额外的存储空间。

比如假定前 $i$ 个的解是 $a_m-a_n$，考虑第 $i+1$ 个，若 $a_m$ 到 $a_i$ 之间有个很小的数 $a_k$，可以使得 $a_{i+1}-a_k$ 比 $a_m-a_n$ 大，同时也比 $a_{i+1}-a_n$ 大。怎么弄？很难办。

退回原始问题，看着有点像求连续最大子数组之和。

想办法把 $\max(a_j - a_i)$ 转化为 $\max(a_i+\cdots+a_j)$。这里我对使用下标使用有点随意。

我们构造如下数组： $$a_1,a_2-a_1,a_3-a_2,\cdots,a_n-a_{n-1}$$

那么连续最大子数组之和就是： $$(a_{i+1}-a_i)+(a_{i+2}-a_{i+1})+\cdots+{a_j-a_{j-1}} = a_j - a_i$$

也就是说，通过构造一个数组，把原问题转化为了一个很容易解决的问题。

新构造的数据没有必要保存下来，只需要将处理连续最大子数组之和程序中 sum += a[i]; 修改为 sum += (a[i] - a[i-1]) 即可。