如何为这个功能做 O(n) 时间？

Question

我有一个数组。该数组包含股票的价值。

例如；

0. 索引 -> 第一天
1. 索引 -> 1.天
2. 索引 -> 2. 天 . . . 名词索引 -> n。日

而且这个函数应该是计算最高利润。别忘了，它可以先买后卖。购买日必须在销售日之前。

我正在尝试为此功能寻找最佳解决方案。能不能O(n)时间。现在，这个函数的时间复杂度是 O(n^2).

    public static int getResult(int[] array) {
    int result = Integer.MIN_VALUE;
    for (int i = 0; i < array.length; i++) {
        for (int j = i; j < array.length; j++) {
            int diff = array[j] - array[i];
            if (diff > result) {
                result = diff;
            }
        }
    }

    return result;
}

Answer 1

这可以在 O(n) 时间内完成。遍历数组以查找最大和最小的数字。最后return他们的区别。

---

当你迭代时，如果这个数字低于最后一个低的数字，你会记住这个数字和它在某种堆栈或节点数据结构中的最高差异。最后你return最高的数字。