【答案解析】解法一：分治法。
把数组分成两个子数组，其实没有必要拿左边子数组中较小的数字去和右边子数组中较大的数字作减法。可以想象，数对之差的最大值只可能是下面三种情况之一：①被减数和减数都在第一个子数组中，即第一个子数组中的数对之差的最大值；②被减数和减数都在第二个子数组中，即第二个子数组中数对之差的最大值；③被减数在第一个子数组中，是第一个子数组的最大值。减数在第二个子数组中，是第二个子数组的最小值。这三个差值的最大者就是整个数组中数对之差的最大值。
在前面提到的三种情况中，得到第一个子数组的最大值和第二子数组的最小值不是一件难事，但如何得到两个子数组中的数对之差的最大值?这其实是原始问题的子问题，可以递归地解决。下面是这种思路的参考代码：
int MaxDiff_Solutionl(int numberS[], unsiqned length)
{
if(numbers==NULL||length＜2)
return 0;
int max, min;
return MaxDiffCore(numbers, numbers+length-1, &max, &min);
}
int MaxDiffCore(int* start, int* end, int* max, int* min)
{
if(end==start)
{
*max=*min=*start;
return 0;
}
int* middle=start+(end-start)/2;
int maxLeft, minLeft;
int leftDiff=MaxDiffCore(start, middle, &maxLeft, &minLeft);
int maxRight, minRight;
int rightDiff=MaxDiffCore(middle+1, end, &maxRight, &minRight);
int crossDiff=maxLeft-minRight;
*max=(maxLeft＞maxRight)? maxLeft: maxRight;
*min=(minLeft＜minRight)? minLeft: minRight;
int maxDiff=(leftDiff＞rightDiff)? leftDiff: rightDiff;
maxDiff=(maxDiff＞crossDiff)? maxDiff: crossDiff;
return maxDiff;
}
在函数MaxDiffCore中，我们先得到第一个子数组中的最大的数对之差leflDiff，再得到第二个子数组中的最大数对之差rightDiff。接下来用第一个子数组的最大值减去第二个子数组的最小值得到crossDiff。这三者的最大值就是整个数组的最大数对之差。
解法二：动态规划法。
定义diif[i]是以数组中第i个数字为减数的所有数对之差的最大值。也就是说对于任意h(h＜i)，diff[i]≥number[h]-number[i]。diff[i](0≤i＜n)的最大值就是整个数组最大的数对之差。
假设我们已求出diff[i]，该怎么求diff[i+1]呢?对于diff[i]，肯定存在一个h(h＜i)，满足number[h]减去number[i]之差是最大的，也就是number[h]应该是number[i]之前的所有数字的最大值。当求diff[i+1]的时候，需要找到第i+1个数字之前的最大值。第i+1个数字之前的最大值只有两种可能：这个最大值可能是第i个数字之前的最大值，也可能这个最大值就是第i个数字。第i+1个数字之前的最大值肯定是这两者的较大者。我们只要拿第i+1个数字之前的最大值减去number[i+1]，就得到了diff[i+1]。
int MaxDiff Solution2(int numbers[], unsigned length)
{
if(numbers==NULL||length＜2)
return 0;
int max=numbers[0]; //第i个数之前的最大值
int maxDiff=max-numbers[1]; //maxDiff表示diff[i-1]
for(int i=2; i＜length; ++i)
{
if(numbers[i-1]＞max) //第i个数和之前的最大值比较
max=numbers[i-1];
int currentDiff=max-numbers[i]; //currentDiff表示diff[i]
if(currentDiff＞maxDiff)
maxDiff=currentDiff;
}
return msxDiff;
}
上述两种解法，虽然思路不同，但时间复杂度都是O(n)(第一种解法的时间复杂度可以用递归公式表示为T(n)=2(n/2)+O(1)，总体的时间复杂度为O(n))。
暴力法：让每一个数字逐个减去它右边的所有数字，并通过比较得到数对之差的最大值。由于每个数字需要和它后面的O(n)个数字作减法，因此总的时间复杂度是O(n ² )。