数组中数对差最大
题目：
数组中某数字减去其右边的某数字得到一个数对之差，求所有数对之差的最大值。
例如：
数组
{2, 4, 1, 16, 7, 5, 11, 9}
中，数对之差的最大值是
11
（16 - 5）
分析：
看到这个题目，很多人的第一反应是找到这个数组的最大值和最小值，然后觉得最大值减去最小值就是最终的结果。
但由于我们无法保证最大值一定位于数组的左边，因此这个思路不管用。
让每一个数字逐个减去它右边的所有数字，并通过比较得到数对之差的最大值，
总的时间复杂度是
O(n
2
)
。
解法1：分治法（递归实现）
通常蛮力法不会是最好的解法，我们想办法减少减法的次数。假设我们把数组分成两个子数组，我们其实没有必要拿左边的子数组中较大的数字去和右边的子数组中较小的数字作减法，因为数对之差的最大值只有可能是下面三种情况之一
（
1
）被减数和减数都在第一个子数组中，即第一个子数组中的数对之差的最大值；
（
2
）被减数和减数都在第二个子数组中，即第二个子数组中数对之差的最大值；
（
3
）被减数在第一个子数组中，是第一个子数组的最大值；减数在第二个子数组中，是第二个子数组的最小值。
（
1
）、
（
2
）、
（
3
）中，
这三个差值的最大者就是整个数组中数对之差的最大值。
在前面提到的三种情况中，得到第一个子数组的最大值和第二子数组的最小值不是一件难事，但如何得到两个子数组中的数对之差的最大值？这其实是原始问题的子问题，我们可以递归地解决，参考代码：
// 解法1： 分治法（递归实现）
int MaxDiff_Find(int *start, int *end, int *max, int *min)
{
if(start >= end){ // 递归结束条件
*max = *min = *start;
return 0x80000000; // -2147483648
}
int *mid = start + (end - start)/2;
int maxLeft, minLeft;
int leftDiff = MaxDiff_Find(start, mid, &maxLeft, &minLeft); // 左子数组
int maxRight, minRight;
int rightDiff = MaxDiff_Find(mid+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;
}
int MaxDiff(int array[], unsigned int len)
{
if(NULL == array || len < 2){
return -1;
}
int max, min;
int MaxDiff_Num = MaxDiff_Find(array, array+len-1, &max, &min);
printf("maxDiff_Num: %d\n\n", MaxDiff_Num);
}
解法2：转化法（
求子数组的最大和问题
）
较为深入分析此问题，发现可以转化成求子数组最大和问题。
1、有一数组array[n]，数组长度为n
2、构建一个长度为n-1的辅助数组array2[n-1]，且array2[i] = array[i] - array[i+1]; （0<=i<n-1）
3、如果累加辅助数组array2从i到j（j>i），即array[i] + array2[i+1] + ... + array2[j]，
有(array[i] - array[i+1]) + (array[i+1] -array[i+2]) + ... + (array[j] - array[j+1])
= array[i] - array[j+1]
分析至此，发现数组中最大的数对之差（即
array[i] - array[j+1]
）其实是辅助数组
array2
中最大的连续子数组之和。如何求连续子数组最大之和，见前一篇博客
数组中最大和的子数组
，在此直接给出参考代码：
// 解法2： 转化求解子数组的最大和问题
int MaxDiff(int array[], unsigned int len)
{
if(NULL == array || len < 2){
return -1;
}
int *array2 = new int[len - 1]; // 辅助数组
int i = 0;
for(i=0; i<len-1; i++){
array2[i] = array[i] - array[i+1]; // 分解成子问题
}
int curSum = 0 ;
int maxSum = 0x80000000; // -2147483648
for(i=0; i<(len-1); i++){
if(curSum <= 0){
curSum = array2[i]; // 小于或等于零，则重新初始化
}else{
curSum += array2[i]; // 计算累加和
}
if(curSum > maxSum){ // 筛选最大和
maxSum = curSum;
}
}
if(array2){
delete []array2;
array2 = NULL;
}
printf("maxSum: %d\n", maxSum);
}
解法3：动态规划法
解法2，既然可以把求最大的数对差转换成求子数组的最大和，而子数组的最大和可以通过动态规划求解，那是不是可以通过动态规划直接求解呢？下面我们试着用动态规划法直接求数对之差的最大值。
1、定义maxDiff[1]
是以数组中第
i
个数字为减数的所有数对之差的最大值，也就是说对于任意
j
（
j < i
），maxDiff[1]
≥array[j]-array[i]
。以此类推，
maxDiff
[i]
（
0≤i<n
）的最大值就是整个数组最大的数对之差。
2、现在我们
假设
已经求得了
maxDiff
[i]
，我们该怎么求得
maxDiff
[i+1]
呢？对于
maxDiff
[i]
，肯定存在一个
j
（
j < i
），满足
array[j]
减去
array[i]
之差是最大的，也就是
array[j]
应该是
array[i]
之前的所有数字的最大值。当我们求
maxDiff[i+1]
的时候，我们需要找到第
i+1
个数字之前的最大值。
第
i+1
个数字之前的最大值有两种可能：
这个最大值可能是第
i
个数字之前的最大值，也有可能这个最大值就是第
i
个数字。
第
i+1
个数字之前的最大值肯定是这两者的较大者，
我们只要拿第
i+1
个数字之前的最大值减去
array[i+1]
，就得到了
maxDiff[i+1]
。参考代码：
// 解法3： 动态规划法
void MaxDiff(int array[], unsigned int len)
{
if(NULL == array || len < 2){
return;
}
int max = array[0];
int maxDiff = max - array[1]; // 初始化数对差(array[0]-array[1])
int i = 0;
for(i=2; i<len; i++){
if(array[i-1] > max){
max = array[i-1]; // 取数组左侧元素最大值
}
int curDiff = max - array[i]; // 始终用最大值 - 右侧元素值
if(curDiff > maxDiff){ // 判断是否是最大数对差
maxDiff = curDiff;
}
}
printf("maxNum: %d\n", maxDiff);
}
测试结果：
解法小结：
上述三种解法，虽然思路各不相同，但时间复杂度都是
O(n)
第一种方法是基于递归实现，而递归调用是有额外的时间、空间消耗的（比如在调用栈上分配空间保存参数、临时变量等）。
第二种方法需要一个长度为
n-1
的辅助数组，因此其空间复杂度是
O(n)
。
第三种方法则没有额外的时间、空间开销，并且它的代码是最简洁的，因此这是最值得推荐的一种解法。
原文： 数组中数对差最大
版权所有: 本文系米扑博客原创、转载、摘录，或修订后发表，最后更新于 2011-12-28 10:08:56
侵权处理: 本个人博客，不盈利，若侵犯了您的作品权，请联系博主删除，莫恶意，索钱财，感谢！
转载注明: 数组中数对差最大 （米扑博客）