java - 在充满随机数的数组中找到最大的增量

Question

例如，给定一个数组 [3,5,8,10,6,12,4]。你要找到两对元素 i 和 j 之间最大可能的增加，其中 j > i。

在上述情况下，答案将返回 9 -> 12 - 3 = 9。

所以我想到了一个明显的解决方案，即 O(N^2)。 这是我的代码

public class Max {

    public static void main(String[] args) {

        int[] array = {3,5,8,10,6,12,4};

        System.out.println(getMax(array));


    }


    public static int getMax(int [] arr)
    {
        int maxVal = 0;

        for(int i = arr.length-1; i>0; i--)
        {
            for(int j = 0; j<i; j++)
            {
                if(arr[i]-arr[j] > maxVal)
                {

                    maxVal = arr[i] - arr[j];
                }
            }

        }

        return maxVal;
    }

}

但是我想知道是否有可能改进 O(NlogN) 的解决方案，因为如果我们使用分而治之的方法呢？有人可以指导我吗？

更新 我根本找不到最大值和最小值，因为 j 的索引必须大于索引 i。如果我只是简单地寻找最大值和最小值，那么我可能会遇到索引 i 大于索引 j 的情况，这是不允许的。

Answer 1

保持最小值并相应地更新:

min = array[0]
max_diff = 0
for each element e, starting from the second:
  if e - min > max_diff:
    max_diff = e - min
  if e < min:
    min = e