数对之差的最大值(8)

题目：在数组中，数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中，数对之差的最大值是11，是16减去5的结果。

分析：看到这个题目，很多人的第一反应是找到这个数组的最大值和最小值，然后觉得最大值减去最小值就是最终的结果。这种思路忽略了题目中很重要的一点：数对之差是一个数字减去它右边的数字。由于我们无法保证最大值一定位于数组的左边，因此这个思路不管用。

于是我们接下来可以想到让每一个数字逐个减去它右边的所有数字，并通过比较得到数对之差的最大值。由于每个数字需要和它后面的O(n)个数字作减法，因此总的时间复杂度是O(n²)。

解法一：分治法

通常蛮力法不会是最好的解法，我们想办法减少减法的次数。假设我们把数组分成两个子数组，我们其实没有必要拿左边的子数组中较小的数字去和右边的子数组中较大的数字作减法。我们可以想象，数对之差的最大值只有可能是下面三种情况之一：（1）被减数和减数都在第一个子数组中，即第一个子数组中的数对之差的最大值；（2）被减数和减数都在第二个子数组中，即第二个子数组中数对之差的最大值；（3）被减数在第一个子数组中，是第一个子数组的最大值。减数在第二个子数组中，是第二个子数组的最小值。这三个差值的最大者就是整个数组中数对之差的最大值。

在前面提到的三种情况中，得到第一个子数组的最大值和第二子数组的最小值不是一件难事，但如何得到两个子数组中的数对之差的最大值？这其实是原始问题的子问题，我们可以递归地解决。下面是这种思路的参考代码：

int MaxDiff_Solution1(int numbers[], unsigned 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 0x80000000;

    }

 

    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中，我们先得到第一个子数组中的最大的数对之差leftDiff，再得到第二个子数组中的最大数对之差rightDiff。接下来用第一个子数组的最大值减去第二个子数组的最小值得到crossDiff。这三者的最大值就是整个数组的最大数对之差。

解法二：转化成求解子数组的最大和问题

接下来再介绍一种比较巧妙的解法。如果输入一个长度为n的数组numbers，我们先构建一个长度为n-1的辅助数组diff，并且diff[i]等于numbers[i]-numbers[i+1]（0<=i<n-1）。如果我们从数组diff中的第i个数字一直累加到第j个数字（j > i），也就是diff[i] + diff[i+1] + … + diff[j] = (numbers[i]-numbers[i+1]) + (numbers[i + 1]-numbers[i+2]) + ... + (numbers[j] – numbers[j + 1]) = numbers[i] – numbers[j + 1]。

分析到这里，我们发现原始数组中最大的数对之差（即numbers[i] – numbers[j + 1]）其实是辅助数组diff中最大的连续子数组之和。我们在本系列的博客的第3篇《求子数组的最大和》中已经详细讨论过这个问题的解决方法。基于这个思路，我们可以写出如下代码：

int MaxDiff_Solution2(int numbers[], unsigned length)

{

    if(numbers == NULL || length < 2)

        return 0;

 

    int* diff = new int[length - 1];

    for(int i = 1; i < length; ++i)

        diff[i - 1] = numbers[i - 1] - numbers[i];

 

    int currentSum = 0;

    int greatestSum = 0x80000000;

    for(int i = 0; i < length - 1; ++i)

    {

        if(currentSum <= 0)

            currentSum = diff[i];

        else

            currentSum += diff[i];

 

        if(currentSum > greatestSum)

            greatestSum = currentSum;

    }

 

    delete[] diff;

 

    return greatestSum;

} 

解法三：动态规划法

既然我们可以把求最大的数对之差转换成求子数组的最大和，而子数组的最大和可以通过动态规划求解，那我们是不是可以通过动态规划直接求解呢？下面我们试着用动态规划法直接求数对之差的最大值。

我们定义diff[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_Solution3(int numbers[], unsigned length)

{

    if(numbers == NULL || length < 2)

        return 0;

 

    int max = numbers[0];

    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)。第三种方法则没有额外的时间、空间开销，并且它的代码是最简洁的，因此这是最值得推荐的一种解法。