今天面试被问到这个问题,它的优化方案让我不寒而栗(吹爆了,因为我真的很想去这家公司工作……)
给定一组真实值,每个值代表任意时间段后公司的股票价值,找到最佳买入价及其对应的最佳卖出价(低买高卖)。
为了举例说明,让我们以 Z 公司的股票代码为例:
55.39 109.23 48.29 81.59 105.53 94.45 12.24
需要注意的重要一点是数组在时间上是“排序的”——即随着时间的推移,值被附加到数组的右端。因此,我们的买入价值将(必须)在我们的卖出价值的左侧。
(在上面的例子中,理想的解决方案是在 买入48.29
和卖出105.53
)
我用 O(n 2 ) 的复杂度(在 java 中实现)很容易地想出了简单的解决方案:
// returns a 2-element array: first element is the index in the argument array
// of the best buying price, and the second element is the index of the best
// selling price which, collectively, maximize the trading return
//
// if there is no favorable trading (e.g. prices monotonically fall), null is returned
public int[] maximizeReturn(ArrayList<Double> prices) {
int [] retval = new int[2];
int BUY = 0, SELL = 1;
retval[BUY] = retval[SELL] = -1; // indices of buy and sell prices, respectively
for (int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++) {
double difference = prices.get(j).doubleValue() -
prices.get(i).doubleValue();
if (difference > 0.0) {
if (retval[BUY] < 0 || difference > prices.get(retval[SELL]).doubleValue() -
prices.get(retval[BUY]).doubleValue()) {
retval[BUY] = i;
retval[SELL] = j;
}
}
}
}
return (retval[BUY] > 0 ? retval : null);
}
这就是我搞砸的地方:有一个线性时间 O(n) 解决方案,我完全试图弄清楚它(是的,我知道,失败)。有谁知道如何实现线性时间解决方案?(任何你喜欢的语言)谢谢!
编辑
我想,对于任何有兴趣的人,我今天刚收到消息说我没有得到我面试的工作,他们问我这个问题。:(