题目:
数组中某数字减去其右边的某数字得到一个数对之差,求所有数对之差的最大值。
例如:
数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11(16 - 5)
分析:
看到这个题目,很多人的第一反应是找到这个数组的最大值和最小值,然后觉得最大值减去最小值就是最终的结果。
但由于我们无法保证最大值一定位于数组的左边,因此这个思路不管用。
让每一个数字逐个减去它右边的所有数字,并通过比较得到数对之差的最大值,总的时间复杂度是O(n2)。
解法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)。
第三种方法则没有额外的时间、空间开销,并且它的代码是最简洁的,因此这是最值得推荐的一种解法。
源码
分享到:
相关推荐
在数组中,数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11,是16减去5的结果。
1.给出一个整数数组,求其中任意两个元素之差的最大值。
a) 随机生成一个一维数组,数组元素个数可设置。 b) 对数组值进行求和、标准差、平均数、中位数。 c) 数组元素升序、降序排列 d) 插入、删除数组元素值 e) 输出各计算值
给定一个整数数组,其中元素的取值范围为0到10000,求其中出现次数最多的数。
C++目前实现大位数加减法,支持INT类型数组,并支持单元多位数存储,从而轻松扩展数组存储达到最大位数。如声明十万数组每单元存储一位数则可以运算十万位数,扩展每单元存储8位数则可达到80万位数的运算,INT安全才...
数据结构教程(JAVA语言描述) 求一个含有n个整数元素的数组a[0..n-1]中的最大元素,有这样一种思路:先比较第一个元素,再比较第二个元素,比较过程向中间靠近
C语言程序设计-求一批数中最大值和最小值的差
最大间隙问题 C++代码
从键盘任意输入10个整数,用指针变量作函数参数编程计算最大值和最小值,并返回它们所在数组中的位置。
数组要求为:10个数,平均值为10,数组的标准差为1;(这10个数是整数) import random average_speed=10 standard_deviation=1 n=0 while n<10: speed=random.randint(5,13) n+=1 print(speed,end=",") 我...
问题:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大的数。该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好...我们先取特例,令k=1,那么就是取最大的数,只要扫描一遍数组就可
3、数组求平均数 4、按指定小数精度计算数组平均值 5、获取整体平均值:先分组,计算组内平均值,然后计算整体平均值 6、获取子组平均数,以数组形式返回 7、求整体标准差 8、按指定小数精度获取标准差 9、求移动极...
2.已知元素从小到大排列的两个数组x[]和y[],请写出一个程序算出两个数组彼此之间差的绝对值中最小的一个,这叫做数组的距离。 3.输入一个英文句子,将每个单词的第一个字母改成大写字母。 4、输入两个正整数,输出...
从数组中中得到最大的一个数 //3.从数组中中得到最小的一个数 //4.对输入的两个数字进行交换 //5.将数组内的数进行从小到大排列 //6.将数组内的数进行从大到小排列 //7.阶乘 //8.求和 //9.求平均数 //10.求中位数 //...
编写一个程序,估算所给出n个实数的均值Mean、方差Variance和标准差StdDeviation。 其中: 均值指这些数字的平均值。 计算标准差的公式如下: 这里的σ(x1,…,xn)是x值的标准差,xavg则是这n个值的均值。 ...
Python特别灵活,肯定方法不止一种,这里介绍一种我觉得比较简单的方法。 如下图,使用x == np.max(x) 获得一个掩模... 您可能感兴趣的文章:浅谈Python3 numpy.ptp()最大值与最小值的差python 判断三个数字中的最大值实
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 个连接的字符串 s 组成字符串 S,记作 S = [s,n]。例如,["abc",3]=“abcabcabc”。 如果我们...