求数对之差最大值

int32位 posted @ Oct 25, 2013 03:24:17 PM in algorithm , 2597 阅读
转载请注明：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/若有错误，请多多指正，谢谢！
  • 无匹配
  • 无匹配
Small_feed 评论 (6)
1
[回复]
Clay Lowe 说:
2025年4月19日 02:55

Interesting and interesting information can be found on this topic here      profile worth to see it. Kissimmee Exterminator

2
[回复]
Clay Lowe 说:
2025年4月19日 02:55

I like to recommend exclusively fine plus efficient information and facts, hence notice it: Bed Bug Treatment Orlando

3
[回复]
Clay Lowe 说:
2025年4月19日 02:56

Thanks for writing such a good article, I stumbled onto your blog and read a few post. I like your style of writing... Oviedo Termite Control

4
[回复]
Clay Lowe 说:
2025年4月19日 02:56

It is rather very good, nevertheless glance at the data with this handle. Lakeland Exterminator

5
[回复]
Clay Lowe 说:
2025年7月19日 07:09

Very good topic, similar texts are       I do not know if they are as good as your work out. California family law attorney

6
[回复]
Clay Lowe 说:
2025年8月23日 01:17

Nice information, valuable and excellent design, as share good stuff with good ideas and concepts, lots of great information and inspiration, both of which I need, thanks to offer such a helpful information here. จำนำรถ


登录 *


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