题目:在数组中,数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11,是16减去5的结果。
分析:看到这个题目,很多人的第一反应是找到这个数组的最大值和最小值,然后觉得最大值减去最小值就是最终的结果。这种思路忽略了题目中很重要的一点:数对之差是一个数字减去它右边的数字。由于我们无法保证最大值一定位于数组的左边,因此这个思路不管用。
于是我们接下来可以想到让每一个数字逐个减去它右边的所有数字,并通过比较得到数对之差的最大值。由于每个数字需要和它后面的O(n)个数字作减法,因此总的时间复杂度是O(n2)。
解法一:转化成求解子数组的最大和问题
接下来再介绍一种比较巧妙的解法。如果输入一个长度为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中最大的连续子数组之和。
代码如下:
// MaxDiff.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
int MaxDiff_Solution2(int numbers[], unsigned length)
{
if(numbers == NULL || length < 2)
return 0;
int* diff = new int[length - 1];//长度为n-1的辅助数组diff
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;
}
int MaxDiff_Solution1(int numbers[], unsigned length)
{
if(numbers == NULL || length < 2)
return 0;
int* diff = new int[length - 1];//长度为n-1的辅助数组diff
for(int i = 1; i < length; ++i)
diff[i - 1] = numbers[i - 1] - numbers[i];
int currentSum = 0;
int greatestSum = 0;
for(int i = 0; i < length - 1; ++i)
{
currentSum+=diff[i];
if (currentSum>greatestSum)
{
greatestSum=currentSum;
}
if (currentSum<0)
{
currentSum=0;
}
}
delete[] diff;
return greatestSum;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[]={2, 4, 1, 16, 7, 5, 11, 9};
int len =sizeof(a)/sizeof(int);
cout<<MaxDiff_Solution1(a,len)<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
#运用python实现差分进化算法计算函数最大值 import random import math import numpy as np import random cr = 0.6 Population = np.random.rand(100,2) cycle = 500 hig , low = math.pi , 0 def eval(x): y =...
该代码实现了运用差分进化算法解决目标函数的最小值,这里解决的是目标函数y=x*sin(10*PI*x)+2的最小值,读者可以根据自己的需要进行修改目标函数求解最小值,同时可以修改代码求解最大值。
使用遗传算法求解函数最大值问题
遗传算法(Genetic Algorithms,GA)是一种基于自然选择和自然遗传机制的搜索算法,它是一种有效的解决最优化问题的方法,属于一种进化算法。本实验要求采用简单遗传算法求解如下一元函数的最大值:
用C++实现的遗传算法求函数的最大值,可运行
java语言遗传算法求函数最大值
该资源主要是对于人工智能当中一个经典课题--遗传算法求解函数最大值,其中包含对于该算法的C#代码实例,并且可以直接在visual studio运行,有需要的欢迎下载!!
该算法有助于初学者深入理解遗传算法,运用遗传算法求解最大值问题,求解TSP问题中的最短路径,问题中的求解的函数会在下一个帖子发布,如有问题可以询问QQ1846403892
本文档是matlab遗传算法求最大值,网上很多资源不可以运行,这个可以运行
利用遗传算法求函数sinx最大值,得到函数的最优解
粒子群算法求解函数最大值Matlab实例 优化算法慢慢学系列文章示例代码
遗传算法求最大值代码 具体代码 可直接执行 包括一些数据和具体步骤
此算法适合初学者,采用的是遗传算法里面最普遍的二进制编码方式实现函数最大值的求解,里面基本上每一句代码都有详细的注释,将交叉、变异、数值编码的转换单独编写函数,和主函数分离变为,一个一个的模块,更容易...
遗传算法求函数最大值和最小值matlab源码
利用遗传算法求某函数的最大值matlab
利用遗传算法求多元函数最大值的matlab算法
遗传算法GA求函数最大值,内容是MATLAB压缩包,打开压缩点击主函数即可直接运行。
用matlab编写的程序,用GA算法求最大值,可以用
机器学习报告,解释期望最大值原理,内含python小程序,逻辑通顺,内容充实