给定一个整数数组a[n]，求max{aj … ai}，其中0 <= i < j < n。要求时间复杂度为O(n)，空间复杂度为O(1)。
这道题若没有最后的空间复杂度时间复杂度的要求，很简单，两层循环就能解决了。
这个题看似要使用动态规划，但仔细一想，不好弄，不能使用额外的存储空间。
比如假定前i个的解是am-an，考虑第i+1个，若am到ai之间有个很小的数ak，可以使得a(i+1)-ak比am-an大，同时也比a(i+1)-an大。怎么弄？很难搞。
退回原始问题，看着有点像求连续最大子数组之和。
想办法把max{aj - ai}转化为max{am+…+an}。这里我对使用下标使用有点随意，明白这个意思就好。
我们构造如下数组：
a1,a2-a1,a3-a2,…an-a(n-1)
那么连续最大子数组之和就是：
a(i+1)-ai,a(i+2)-a(i+1),…aj-a(j-1) = aj - ai
也就是说，通过构造一个数组，把原问题转化为了一个很容易解决的问题。
新构造的数据是没有必要保存下来的，只需要将处理连续最大子数组之和程序中sum += ai;修改为sum += (ai - a(i-1))即可。