是否有可能在小于O(n平方公里)复杂度的情况下找到数组中两个数字之间的最大下降量？

Question

我有一个满是数字的数组。我需要找到两个数字之间的最大差异，但最大的数字在数组中最小的数字之前。

public static int maximalDrop (int [] a)

例如：

对于数组5、21、3、27、12、24、7、6、4，结果为23 (27-4)。

对于数组5、21、3、22、12、7、26、14，结果为18 (21-3)。

我的解决方案是取数组中的第一个元素(这个数字很大)，检查这个数字和数组中所有其他数字之间的差异，然后做同样的事情，但是与数组中的下一个数字进行比较，当然，比较差异并返回最大的一个。我认为我的解决方案是O(n平方)，所以我可以少做一点吗？

Answer 1

除非我误解了这个问题，否则我相信你可以在数组的一次传递中做到这一点。您只需要跟踪到到目前为止所看到的最大值和最大差异。在遍历数组时，请计算当前数字与迄今看到的最大值之间的差异。

对于第二个例子5，21，3，22，12，7，26，14

1: 5 is first value so set maximum to 5
2: 21 > 5 so reset maximum
3: 21 - 3 = 18
4: 22 > 21 so reset maximum
5: 22 - 12 = 10
6: 22 - 7  = 15
7: 26 > 22 so reset maximum
8: 26 - 14 = 12

当您发现一个新的最大值时，在数组中超过它的任何较小的数字都需要从这个新的最大值中减去。

所需的答案是在此过程中看到的最大值--在本例中是步骤3中计算的18。

Answer 2

试试这个：

public static int maximalDrop (int[]a)
{
    int max= a[0];
    int dif= 0;
    for (int i=0; i<a.length; i++)
    {
        if(a[i]>max){
            max=a[i];
            if (dif<max-a[i+1])
            {
             dif=max-a[i+1];   
            }
        }
    }
    return dif;    
}

Answer 3

嗯，我不确定我对这个问题的理解是否正确。但是，我认为您只需要跟踪您已经访问过的最大值和下降值。考虑一下，如果a-b造成的最大跌幅，而b之前的另一个值c大于a，那么c-b绝对大于a，那么最大的下降应该是c。尽管以后会有更大的数字替换最大值，但它不会更改drop值，除非它可以进行更大的下降。

这段代码可能有效，它是用java编写的:所以时间成本是O(n)。如果我误解了一些概念，请告诉我。

public int findDrop(int[] ar){ int max = ar[0]; int drop = 0; for(int i=1;i<ar.length;i++){ if(ar[i] > max){ max = ar[i]; } else { if(max - ar[i] > drop){ drop = max - ar[i]; } } } return drop; }