求数对之差最大值

int32位 posted @ Oct 25, 2013 03:24:17 PM in algorithm , 1734 阅读
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

给定一个数组a, 长度n,索引从0开始,定义数对之差为a[i] - a[j], 其中0 <= i < j < n,即数组前面的数减去数组后面任意一个元素。现在要求数对之差的最大值。如数组int a[] = {2, 4, 1, 16, 7, 5, 11, 9},数对之差最大值为11, 16 - 5 的结果。

最直接的方法就是暴力枚举法,即求出所有的数对之差,这样的时间复杂度为O(n2)。那有没有更高效的方法呢?

其实这个和求数组最大连续和有点类似,我们知道如果减少不变,被减数越大,则差越大。于是我们利用动态规划的思想,假定减数固定为数组某个元素,设为a[i],那么与a[i]形成的数对之差最大值就是a[i]前面的最大值(这个最大值我们可以保存在一个临时变量中)减去a[i]的值,我们可以依次遍历整个数组,分别求出与这个元素作为减数的最大数对之差,他们的最大值即为所求。这样只需要遍历数组一遍,时间复杂度为O(n)。附上代码:

#include <stdio.h>
#include <assert.h>
#include <limits.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
static int maxDiff(const int *a, const int n)
{
	assert(a != NULL && n > 1);
	int cur_diff, i;
	int max_diff = INT_MIN;
	int max = INT_MIN;
	for (i = 1; i < n; i++) {
		max = MAX(max, a[i - 1]);
		cur_diff = max - a[i];
		max_diff = MAX(max_diff, cur_diff);
	}
	return max_diff;
}
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter