我想征求你对这个问题的看法:
我有一个数组 A，有 N 个 double 类型的元素(或者整数)。我想找一个复杂度小于 O(N2) 的算法来求:
max A[i] - A[j]
对于 1 < j <= i < n。请注意没有abs()。我想到了:
- 动态规划
- 二分法，分而治之
- 排序后的一些处理以跟踪索引
您有什么意见或想法吗？您能否指出一些好的引用资料来训练或在解决此类算法问题方面取得进展？
最佳答案
对阵列进行三次扫描。首先来自j=2向上，填充辅助数组 a到目前为止，最小 元素。然后，从顶部进行扫描 i=n-1向下，填充(也是从上到下)另一个辅助数组，b ，到目前为止(从顶部开始)最大 元素。现在扫描两个辅助数组，寻找 b[i]-a[i] 的最大差异.
这就是答案。 O(n)总共。你可以说这是一个动态规划算法。
编辑:作为优化，可以去掉第三次扫描和第二次数组，通过维护两个循环变量在第二次扫描中找到答案，max-so-far-from-the-top 和max-difference。
至于一般如何解决这类问题的“指针”，你通常会像你写的那样尝试一些通用方法——分而治之、记忆化/动态规划等。首先仔细看看你的问题和涉及的概念.在这里，它是最大/最小值。将这些概念分开，看看这些部分如何在问题的上下文中组合，可能会改变它们的计算顺序。另一个是在您的问题中寻找隐藏的顺序/对称性。
具体来说，修复任意内点k沿着列表，这个问题被简化为找到所有 j 中最小元素之间的差异。这样 1<j<=k , 和 i 中的最大元素小号:k<=i<n .你在这里看到了分而治之，以及最大/最小的概念(即它们的渐进式计算)，以及各部分之间的相互作用。显示隐藏顺序(k 沿着数组)，内存有助于保存最大/最小值的中间结果。
任意点的固定k可以看作是首先解决一个较小的子问题(“对于给定的 k ...”)，然后看看它是否有任何特殊之处并且可以废除 - generalized - < em>抽象结束。
有一种技术是首先尝试制定和解决一个更大的问题，这样一个原始问题就是这个更大问题的一部分。在这里，我们想到的是找到每个 k 的所有差异，然后从中找到最大的差异。
临时结果的双重用途(既用于比较特定的 k 点，又用于计算其方向的下一个临时结果)通常意味着一些可观的节省。所以，
- 分而治之
- 记忆化/动态规划
- 隐藏顺序/对称
- 拆开概念 - 了解各个部分如何结合
- double use - 找到重复使用的部分并记住它们
- 解决更大的问题
- 尝试任意子问题并对其进行抽象
关于在数组中查找 'maximal difference' 的 C++ 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10793048/