4

我正在询问您对这个问题的想法：

我有一个数组 A，有 N 个类型的元素double（或整数）。我想找到一个复杂度小于 O(N 2 ) 的算法来找到：

    max A[i] - A[j]

对于 1 < j <= i < n。请注意，没有abs(). 我想到了：

  • 动态规划
  • 二分法，分而治之
  • 在跟踪索引后进行一些处理

你有什么意见或想法吗？您能否指出一些好的参考来训练或在解决此类算法问题方面取得进展？

4

4 回答 4

8

对阵列进行三次扫描。首先，到目前为止，用最少的j=2元素填充一个辅助数组。然后，从上到下进行扫描，填充（也从上到下）另一个辅助数组， ，到目前为止（从顶部）具有最大元素。现在对两个辅助数组进行扫描，寻找最大差异。ai=n-1bb[i]-a[i]

那将是答案。O(n)总共。你可以说它是一种动态规划算法。

编辑：作为优化，您可以消除第三次扫描和第二个数组，并通过维护两个循环变量max-so-far-from-the-top和max-difference在第二次扫描中找到答案。

至于一般如何解决此类问题的“指针”，您通常会尝试一些像您写的一般方法 - 分而治之，记忆/动态规划等。首先仔细查看您的问题和涉及的概念。在这里，它是最大值/最小值。将这些概念分开，看看这些部分如何在问题的上下文中组合，可能会改变它们的计算顺序。另一个是在您的问题中寻找隐藏的顺序/对称性。

具体来说，固定列表中的任意内部点k，这个问题被简化为找到所有js 中的最小元素与 s 中1<j<=k的最大元素之间i的差异：k<=i<n。你在这里看到了分而治之，以及分解最大/最小的概念（即它们的渐进式计算），以及各部分之间的相互作用。隐藏的顺序被揭示（k沿着数组），并且记忆有助于保存最大/最小值的中间结果。

任意点的固定k可以看作是首先解决一个较小的子问题（“对于给定的k......”），然后看看它是否有什么特别之处，它可以被废除 -概括-抽象出来。

有一种技术是首先尝试制定和解决更大的问题，这样原始问题就是这个更大问题的一部分。在这里，我们考虑找到每个 k 的所有差异，然后从中找到最大的差异。

中期结果的双重使用（用于比较特定k点，以及计算各自方向的下一个中期结果）通常意味着一些可观的节省。所以，

  • 分而治之
  • 记忆/动态规划
  • 隐藏的顺序/对称
  • 将概念拆开——看看这些部分是如何结合起来的
  • 双重用途 - 找到双重用途的零件并记住它们
  • 解决更大的问题
  • 尝试任意子问题并对其进行抽象
于 2012-05-29T06:17:17.137 回答
4

这应该可以在一次迭代中实现。max(a[i] - a[j])for 1 < j <= i 应该与 相同max[i=2..n](a[i] - min[j=2..i](a[j]))，对吧？a[j]因此，您必须在遍历数组时跟踪最小的，寻找最大的a[i] - min(a[j]). 这样你只有一次迭代，j 将小于或等于 i。

于 2012-05-29T16:40:23.347 回答
1

你只需要遍历数组找到最大值和最小值然后得到差异，所以最坏的情况是线性时间。如果数组已排序，您可以在恒定时间内找到差异，还是我错过了什么？

于 2012-05-29T05:41:09.727 回答
0

Java 实现以线性时间运行

public class MaxDiference {

public static void main(String[] args) {
     System.out.println(betweenTwoElements(2, 3, 10, 6, 4, 8, 1));
}

private static int betweenTwoElements(int... nums) {
    int maxDifference   = nums[1] - nums[0];
    int minElement      = nums[0];

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] - minElement > maxDifference) {
            maxDifference = nums[i] - minElement;
        }
        if (nums[i] < minElement) {
            minElement =  nums[i];
        }           
    }       
    return maxDifference;
}
}
于 2012-10-01T14:26:34.677 回答