寻找A[J] +- A[I]的最大值
我下周就要期末考试了，我要复习以前的笔记和家庭作业/考试，努力学习。在我的第二次作业中，我有一个问题，我弄错了，我只是不确定到底该怎么做。以下是问题所在：
设计有效的算法，获取正数组' a '，并确定: aj + ai的最大值，其中j>或= to i。b. aj - ai的最大值，其中j>或= to i。
我不想要真正的代码，只需要一些伪代码和它的运行时间。
我认为可行的方法是：
查找第一、第二和第三个最大值和最小值。b.对于j>=i，第一最大值a(j) -第一最小值a(i)，对于j>=i
然后，如果上述条件失败，只需重复第二个max，min。
我不知道为什么我不能理解这件事。我知道j可以等于i，所以我的答案会产生a部分的错误结果。对于b部分，假设我有一个数组89| 90 |1|2|3| 4 |5，它应该是90-1= 89，但它应该是5-1=4。我甚至没有尝试考虑运行时间，因为那部分是错误的。
任何帮助或提示都是很棒的。谢谢!
回答 2
Stack Overflow用户
发布于 2013-12-09 04:35:47
答: aj + ai是直接的，它只是2*最大值，因为j可以等于i可以在O(N)中完成
b. aj - ai对于这种情况，我们需要一点动态编程来使其达到O(N)。这里有一个用O(N)表示的方法：-
构建一个数组，使得maxi表示子数组ai到n中的最大元素
max[n] = a[n]
for(i=n-1;i>=1;i--)
max[i] = maximum(max[i+1],a[i]);然后找到作为max a[j]-a[i]的所有i的最大值(max[i]-a[i])。
maxi编辑：刚刚意识到不需要维护数组max[]，你可以使用之前的值来计算maxi - ai。
Stack Overflow用户
发布于 2013-12-09 04:50:45
答:最大ai+aj是在数组中找到最大和第二大值，它很简单，时间复杂度是O(N)。
b.为了最大化aj-ai，对于每个j，可能的最优解是aj -j之前的最小值，所以你只需要保持这个值并更新最优解
mmin = a[0];
ans = 0;
for (int j = 0; j < length(a); ++j){
mmin = min(a[j], mmin);
ans = max(ans, a[j] - mmin);
}
return ans;它也是O(N)。
https://stackoverflow.com/questions/20458462
复制相似问题
腾讯云开发者
