C ++算法来寻找“最大的区别'在一个数组 [英] C++ algorithm to find 'maximal difference' in an array
问题描述
我要求你的想法就这个问题：
I am asking for your ideas regarding this problem:
我有一个数组A，有型的N个元素双（或者整数）。我想找到一个算法的复杂度小于O（N 2 ）找到：
I have one array A, with N elements of type double (or alternatively integer). I would like to find an algorithm with complexity less than O(N2) to find:
max A[i] - A[j]
有关1＆LT; J＆LT; = I＆LT; ñ。请注意，没有 ABS（）。我想到了：
For 1 < j <= i < n. Please notice that there is no abs(). I thought of:
- 动态编程
- 二分法，分而治之
- 指数的排序保持跟踪经过一些治疗
你会有一些意见或想法？你可以点一些不错的裁判训练和进步来解决这样的算法问题？
Would you have some comments or ideas? Could you point at some good ref to train or make progress to solve such algorithm questions?
推荐答案
请通过数组3个扫描。首先从 J = 2 起来，填补了辅助阵列 A 与最小的元素为止。然后，从顶部做扫描 I = N-1 下来，灌装（也从上往下）另一个辅助阵列， B ，用的最大的元素为止（从顶部）。现在做两个辅助阵列的扫描，寻找 B的最大区别[I] -a [I] 。
Make three sweeps through the array. First from j=2 up, filling an auxiliary array a with minimal element so far. Then, do the sweep from the top i=n-1 down, filling (also from the top down) another auxiliary array, b, with maximal element so far (from the top). Now do the sweep of the both auxiliary arrays, looking for a maximal difference of b[i]-a[i].
这将是答案。 O（N）的总和。你可以说这是一个动态规划算法。
That will be the answer. O(n) in total. You could say it's a dynamic programming algorithm.
修改 作为一种优化，可以消除第三扫描和第二阵列，并找到在第二扫答案通过维护两个循环变量，最大那么远，从最顶端和最大差的。
至于指针关于如何解决一般这样的问题，你通常会尝试一些，就像你写的一般方法 - 分而治之，记忆化/动态规划等首先仔细查看你的问题和所涉及的概念。这里，是最大值/最小值。把这些概念拆开，看看这些部分组合到问题的背景下，有可能改变他们正在计算顺序。另一种是寻找你的问题隐藏订单/对称性。
As for "pointers" about how to solve such problems in general, you usually try some general methods just like you wrote - divide and conquer, memoization/dynamic programming, etc. First of all look closely at your problem and concepts involved. Here, it's maximum/minimum. Take these concepts apart and see how these parts combine in the context of the problem, possibly changing order in which they're calculated. Another one is looking for hidden order/symmetries in your problem.
具体而言，固定了的任意的内部点 K 沿列表中，这个问题被归结为寻找在所有的最小元素之间的差异Ĵ S，从而使 1＆LT; J＆LT; = K ，并跻身 K＆LT; = I n种。你看，分而治之的位置，以及拆开最大/最小（即他们的进步的计算）的概念，和各部分之间的相互作用。隐藏的顺序显示（ K 随之而来阵列），以及记忆化有助于保存中间结果最大/最小值。
Specifically, fixing an arbitrary inner point k along the list, this problem is reduced to finding the difference between the minimal element among all js such that 1<j<=k, and the maximal element among is: k<=i<n. You see divide-and-conquer here, as well as taking apart the concepts of max/min (i.e. their progressive calculation), and the interaction between the parts. The hidden order is revealed (k goes along the array), and memoization helps save the interim results for max/min values.
任意点的固定 K 可以被看作是第一个（解决一个较小的子问题对于给定的 K ...），并查看是否有什么特别的地方，它可以被取消 - 通用 - 抽象的过
The fixing of arbitrary point k could be seen as solving a smaller sub-problem first ("for a given k..."), and seeing whether there is anything special about it and it can be abolished - generalized - abstracted over.
有试图制定并首先解决一个更大的问题，使得原来的问题是这个更大的一个部分的技术。在这里，我们认为发现了的所有的差异为每K，然后发现从他们最大的。
There is a technique of trying to formulate and solve a bigger problem first, such that an original problem is a part of this bigger one. Here, we think of find all the differences for each k, and then finding the maximal one from them.
在两用的临时结果（使用这两种比较具体的 K 点，并在计算的下一步每一个在它的方向中期业绩）通常指的是一些相当大的节约。因此，
The double use for interim results (used both in comparison for specific k point, and in calculating the next interim result each in its direction) usually mean some considerable savings. So,
- 分而治之的
- 在记忆化/动态编程
- 在隐藏的订单/对称性
- 以概念分开 - 参观了解各部分结合
- 双击使用 - 发现部分双用途和memoize的他们
- 在解决一个更大的问题
- 在尝试任意子问题，并提取了它
这篇关于C ++算法来寻找“最大的区别'在一个数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
