int32bit
公告
外部文章迁移完毕文章分类
最新评论
最新留言
友情链接
RSS
功能
热门文章
随机文章
存档
访问次数
328245
求数对之差最大值
int32位
posted @ Oct 25, 2013 03:24:17 PM
in algorithm
, 2406 阅读
转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！转载请注明：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;
}
评论 (0)