题目:在数组中,数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11,是16减去5的结果。
分析:看到这个题目,很多人的第一反应是找到这个数组的最大值和最小值,然后觉得最大值减去最小值就是最终的结果。这种思路忽略了题目中很重要的一点:数对之差是一个数字减去它右边的数字。由于我们无法保证最大值一定位于数组的左边,因此这个思路不管用。
于是我们接下来可以想到让每一个数字逐个减去它右边的所有数字,并通过比较得到数对之差的最大值。由于每个数字需要和它后面的O(n)个数字作减法,因此总的时间复杂度是O(n2)。
解法一:分治法 通常蛮力法不会是最好的解法,我们想办法减少减法的次数。假设我们把数组分成两个子数组,我们其实没有必要拿左边的子数组中较小的数字去和右边的子数组中较大的数字作减法。我们可以想象,数对之差的最大值只有可能是下面三种情况之一:(1)被减数和减数都在第一个子数组中,即第一个子数组中的数对之差的最大值;(2)被减数和减数都在第二个子数组中,即第二个子数组中数对之差的最大值;(3)被减数在第一个子数组中,是第一个子数组的最大值。减数在第二个子数组中,是第二个子数组的最小值。这三个差值的最大者就是整个数组中数对之差的最大值。
在前面提到的三种情况中,得到第一个子数组的最大值和第二子数组的最小值不是一件难事,但如何得到两个子数组中的数对之差的最大值?这其实是原始问题的子问题,我们可以递归地解决。下面是这种思路的参考代码:
int MaxDiff_Solution1(int numbers[], unsigned length)
{
if(numbers == NULL || length < 2)
return 0;
int max, min;
return MaxDiffCore(numbers, numbers + length - 1, &max, &min);
}
int MaxDiffCore(int* start, int* end, int* max, int* min)
{
if(end == start)
{
*max = *min = *start;
return 0x80000000;
}
int* middle = start + (end - start) / 2;
int maxLeft, minLeft;
int leftDiff = MaxDiffCore(start, middle, &maxLeft, &minLeft);
int maxRight, minRight;
int rightDiff = MaxDiffCore(middle + 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;
}
在函数MaxDiffCore中,我们先得到第一个子数组中的最大的数对之差leftDiff,再得到第二个子数组中的最大数对之差rightDiff。接下来用第一个子数组的最大值减去第二个子数组的最小值得到crossDiff。这三者的最大值就是整个数组的最大数对之差。
解法二:转化成求解子数组的最大和问题 接下来再介绍一种比较巧妙的解法。如果输入一个长度为n的数组numbers,我们先构建一个长度为n-1的辅助数组diff,并且diff[i]等于numbers[i]-numbers[i+1](0<=i<n-1)。如果我们从数组diff中的第i个数字一直累加到第j个数字(j > i),也就是diff[i] + diff[i+1] + … + diff[j] = (numbers[i]-numbers[i+1]) + (numbers[i + 1]-numbers[i+2]) + ... + (numbers[j] – numbers[j + 1]) = numbers[i] – numbers[j + 1]。
分析到这里,我们发现原始数组中最大的数对之差(即numbers[i] – numbers[j + 1])其实是辅助数组diff中最大的连续子数组之和。我们在本系列的博客的第3篇《求子数组的最大和》中已经详细讨论过这个问题的解决方法。基于这个思路,我们可以写出如下代码:
int MaxDiff_Solution2(int numbers[], unsigned length)
{
if(numbers == NULL || length < 2)
return 0;
int* diff = new int[length - 1];
for(int i = 1; i < length; ++i)
diff[i - 1] = numbers[i - 1] - numbers[i];
int currentSum = 0;
int greatestSum = 0x80000000;
for(int i = 0; i < length - 1; ++i)
{
if(currentSum <= 0)
currentSum = diff[i];
else
currentSum += diff[i];
if(currentSum > greatestSum)
greatestSum = currentSum;
}
delete[] diff;
return greatestSum;
}
解法三:动态规划法
既然我们可以把求最大的数对之差转换成求子数组的最大和,而子数组的最大和可以通过动态规划求解,那我们是不是可以通过动态规划直接求解呢?下面我们试着用动态规划法直接求数对之差的最大值。 我们定义diff[i]是以数组中第i个数字为减数的所有数对之差的最大值。也就是说对于任意h(h < i),diff[i]≥number[h]-number[i]。diff[i](0≤i<n)的最大值就是整个数组最大的数对之差。 假设我们已经求得了diff[i],我们该怎么求得diff[i+1]呢?对于diff[i],肯定存在一个h(h < i),满足number[h]减去number[i]之差是最大的,也就是number[h]应该是number[i]之前的所有数字的最大值。当我们求diff[i+1]的时候,我们需要找到第i+1个数字之前的最大值。第i+1个数字之前的最大值有两种可能:这个最大值可能是第i个数字之前的最大值,也有可能这个最大值就是第i个数字。第i+1个数字之前的最大值肯定是这两者的较大者。我们只要拿第i+1个数字之前的最大值减去number[i+1],就得到了diff[i+1]。 int MaxDiff_Solution3(int numbers[], unsigned length) { if(numbers == NULL || length < 2) return 0; int max = numbers[0]; int maxDiff = max - numbers[1]; for(int i = 2; i < length; ++i) { if(numbers[i - 1] > max) max = numbers[i - 1]; int currentDiff = max - numbers[i]; if(currentDiff > maxDiff) maxDiff = currentDiff; } return maxDiff; } 在上述代码中,max表示第i个数字之前的最大值,而currentDiff表示diff[i] (0≤i<n),diff[i]的最大值就是代码中maxDiff。 解法小结 上述三种代码,虽然思路各不相同,但时间复杂度都是O(n)(第一种解法的时间复杂度可以用递归公式表示为T(n)=2(n/2)+O(1),所以总体时间复杂度是O(n))。我们也可以注意到第一种方法是基于递归实现,而递归调用是有额外的时间、空间消耗的(比如在调用栈上分配空间保存参数、临时变量等)。第二种方法需要一个长度为n-1的辅助数组,因此其空间复杂度是O(n)。第三种方法则没有额外的时间、空间开销,并且它的代码是最简洁的,因此这是最值得推荐的一种解法。
发表评论
-
析构函数为虚函数的原因
2012-09-09 11:42 783我们知道,用C++开发的时候,用来做基类的类的析构函数 ... -
hash的应用
2012-08-31 23:02 921第一部分为一道百度面试题Top K算法的详解;第二部分为关 ... -
微软智力题
2012-08-29 19:59 537第一组1.烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有 ... -
C++不能被继承的类
2012-08-27 20:16 994一个类不能被继承, ... -
括号对齐问题
2012-08-27 10:47 1349解法一:左右括号成一对则抵消 可以 ... -
树的遍历
2012-08-19 10:43 672/****************************** ... -
堆排序
2012-08-16 14:24 841堆:(二叉)堆数据结构是一种数组对象。它可以被视为一棵完全 ... -
多态赋值
2012-08-14 16:16 775#include <iostream> usi ... -
static变量与static函数(转)
2012-08-13 10:15 698一、 static 变量 static变量大致分为三种用法 ... -
不用sizeof判断16位32位
2012-08-10 15:21 1658用C++写个程序,如何判断一个操作系统是16位还是3 ... -
找出连续最长的数字串(百度面试)
2012-08-09 15:15 1108int maxContinuNum(const char*in ... -
顺序栈和链栈
2012-08-06 10:01 763顺序栈:话不多说直接上代码 #include ... -
队列的数组实现和链表实现
2012-08-05 16:20 991话不多少,数组实现上代码: #include<i ... -
KMP算法详解
2012-08-02 21:40 847KMP算法: 是在一个“主文本字符串” ... -
字符串的最长连续重复子串
2012-08-01 15:05 9696两种方法: 循环两次寻找最长的子串: <方法一> ... -
寻找一个字符串连续出现最多的子串的方法(转)
2012-07-31 21:19 914算法描述首先获得后缀数组,然后1.第一行第一个字符a,与第二行 ... -
字符串的循环移位
2012-07-31 16:52 931假设字符串:abcdefg 左循环两位:cdefgab 右 ... -
一次谷歌面试趣事(转)
2012-07-31 15:26 724很多年前我进入硅谷 ... -
约瑟夫环问题(循环链表)
2012-07-30 21:31 1237题目描述:n只猴子要选大王,选举方法如下:所有猴子按 1, ... -
面试之单链表
2012-07-30 20:18 6881、编程实现一个单链表的建立/测长/打印。 ...
相关推荐
在数组中,数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11,是16减去5的结果。
1112:最大值和最小值的差 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 24329 通过数: 14187 【题目描述】 ...输出M个数中最大值和最小值的差。 【输入样例】 5 2 5 7 4 2 【输出样例】 5 【来源】 NO
比较数的最大值和最小值,别种方法--通过调换前后顺序来提高查找效率.
数组中某数字减去其右边的某数字得到一个数对之差,求所有数对之差的最大值。
给定一个整数数组,其中元素的取值范围为0到10000,求其中出现次数最多的数。
C语言程序设计-求一批数中最大值和最小值的差
1.给出一个整数数组,求其中任意两个元素之差的最大值。
从键盘任意输入10个整数,用指针变量作函数参数编程计算最大值和最小值,并返回它们所在数组中的位置。
给定一组正整数,其中的最大值和最小值分别为max和min,其中的一个数x到max和min的距离差D定义为 abs(abs(x-max) - abs(x-min))。 其中,abs()表示求一个数的绝对值 输入 输入第一行为整数n,剩余n行每行一个正...
如何查看Pandas DataFrame对象列的最大值、最小值、平均值、标准差、中位数等 我们举个例子说明一下,先创建一个dataframe对象df,内容如下: 1.使用sum函数获得函数列的和,用法:df.sum() 2.使用max获取最大值,用法...
西西弗斯黑洞【123数字黑洞】 /// 设定一个任意数字串,数出这个数中的偶数个数,奇数个数,及这个数中所包含的所有位数的总数 ... /// 对三位数继续计算最大值 和 最小值,最终差值(终结黑洞值)为495
值总和最小值最大值标准差 1、数据来源:Atmospheric Composit ion Analysis Group 2、数据时间:1998-2021年 3、数 据范围:包含三个文件分别为: ①全国34省(含港澳台) ②全国371地级市城市自 治州盟地区 ③全国...
numpy.ptp() 是计算最大值与最小值差的函数,用法如下: import numpy as np a = np.array([np.random.randint(0, 20, 5), np.random.randint(0, 20, 5)]) print('原始数据\n'a) print('对所有数据计算\n', a.ptp()...
编写一个程序,估算所给出n个实数的均值Mean、方差Variance... 这里的σ(x1,…,xn)是x值的标准差,xavg则是这n个值的均值。 方差是标准差的平方。 要求: n个实数采取手工输入; 使用表1、2、3提供的数据进行测试。
)就像进行数据处理的时候,有时会遇到求极值(最大值、最小值)、平均值、中位数和四分位数(25%、 75%)的情况。 这一篇博客就是你的福音,让你绝对0基础使用python 进行数据分析。 1、下载py的环境。 这里引用一...
Python特别灵活,肯定方法不止一种,这里介绍一种我觉得比较简单的方法。 如下图,使用x == np.max(x) 获得一个掩模... 您可能感兴趣的文章:浅谈Python3 numpy.ptp()最大值与最小值的差python 判断三个数字中的最大值实
【求助】最近在学Python,要做一个仿真实验,需要设定10kn(1kn≈0.5m/s)的船舶的平均航速,因为要具有随机性,所以我就想用Python的random.randint来实现,但是不知道怎么才能把这组数的平均值和标准差给固定 ...
首先,计算某一尺度窗口的平均灰度值 ,然后判断每一个像素的灰度 ,若大于灰度平均值 ,则累加其灰度值为 max ,若小于灰度平均值 ,则累加其灰度值为min ,用max 和min代替 在 Sarkar 和 Chaudhuri 算法中的最大值和...
中国人口空间分布省级面板数据集:年份 省代码 省份 均值 总和 标准差 最小值 最大值 非零像元数 非缺失像元数 中国人口空间分布市级面板数据集:年份 省代码 省 市代码 市 均值 总和 标准差 最小值 最大值 非零像元...
差分格式是数值计算方法中微分以及偏微分导数的一种离散化方法,即用相邻两个或者多个数值点的差分取代偏微分方程中导数或者偏导数的一种算法。 选择差分格式是离散化偏微分方程的第一步。本文是五点差分格式代码