数组中数对差最大

题目：

数组中某数字减去其右边的某数字得到一个数对之差，求所有数对之差的最大值。

例如：

数组{2, 4, 1, 16, 7, 5, 11, 9}中，数对之差的最大值是11（16 - 5）

分析：

看到这个题目，很多人的第一反应是找到这个数组的最大值和最小值，然后觉得最大值减去最小值就是最终的结果。

但由于我们无法保证最大值一定位于数组的左边，因此这个思路不管用。

让每一个数字逐个减去它右边的所有数字，并通过比较得到数对之差的最大值，总的时间复杂度是O(n²)。

解法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)。

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

源码