这个函数怎么做O(n)时间?

Question

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

例如,

0. Index ->第一天
1. 指数→1. 天
2. 指数→2. 一天．．．n.索引->n。天

And此函数应计算最高利润。别忘了，它可以先买后卖。购买日期必须在销售日期之前。

我正试图找到这个函数的最佳解决方案。可以是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)时间内完成。遍历数组，寻找最大和最小的数字。最后返回它们之间的差值

---

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

Answer 2

这是一个O(n)方法，其结果与您的代码相同。创建与第一个大小相同的第二个数组(minThruArr)，遍历数组，并将迄今为止看到的最小值放入新数组中。这个数组是该元素之前的最小值。然后，向后遍历初始数组，跟踪到目前为止看到的最大值(maxThru)。对于每个这样的索引，从通过该索引的最大值(maxThru - minThru[i])减去通过该索引的最小值。跟踪最大值，这就是你的结果。

public static int getResult(int[] array) {
int[] minThruArr = new int[array.length];
int min = Integer.MAX_VALUE;
for (int i = 0; i < array.length; i++) {
min = Math.min(min, array[i]);
minThruArr[i] = min;
}
int result = Integer.MIN_VALUE;
int maxThru = Integer.MIN_VALUE;
for (int i = array.length - 1; i >= 0; i--) {
maxThru = Math.max(maxThru, array[i]);
result = Math.max(result, maxThru - minThruArr[i]);
}
return result;
}