int maxDiff = max - numbers[1];
for(int i = 2; i < length; ++i)
{
if(numbers[i - 1] > max)
max = numbers[i - 1];
int currentDiff = max - numbers[i];
if(currentDiff > maxDiff)
maxDiff = currentDiff;
}
return maxDiff;
}
在上述代码中，max表示第i个数字之前的最大值，而currentDiff表示diff[i] （0≤i<n），diff[i]的最大值就是代码中maxDiff。
解法小结
上述三种代码，虽然思路各不相同，但时间复杂度都是O(n)（第一种解法的时间复杂度可以用递归公式表示为T(n)=2(n/2)+O(1)，所以总体时间复杂度是O(n)）。我们也可以注意到第一种方法是基于递归实现，而递归调用是有额外的时间、空间消耗的（比如在调用栈上分配空间保存参数、临时变量等）。第二种方法需要一个长度为n-1的辅助数组，因此其空间复杂度是O(n)。第三种方法则没有额外的时间、空间开销，并且它的代码是最简洁的，因此这是最值得推荐的一种解法。