在面试中遇到这个问题。想知道有没有更好的解决办法:
给定股票价格序列 [p1, p2, p3, p4, …. pN].交易员乔被要求在时间 i 购买 1 股股票，并在时间 j 出售相同的股票。他的目标是最大化买入时间和卖出时间之间的时间间隔，但仍然有利可图。 例如，Trade Joe 按时间顺序给出了一系列价格:
Time,Price
10:00,10.3
10:01,10.1
10:02,11
10:03,13
10:04,9.5
10:05,7.3
10:06,8
10:07,10.2
10:08,9.8
如果他在 10:01 买入股票，价格 = 10.1，并在 10:07 卖出，价格 10.2。他将获利 0.1，买卖之间的时间为 6 分钟。这是此示例的最长时间。
输入
第一行包含序列的长度 N。接下来的 N 行包含 (time, price) 对: 否 时间1，价格1 时间2，价格2 ……
输出
使用给定的价格序列，有利可图的买卖行为之间的最长时间
示例输入(使用文件或标准输入):
7
10:01,7
10:02,4
10:03,5
10:04,10
10:05,5
10:06,2
10:07,6
示例输出:
5 (This is using a buy at 10:02 ($4) and a sell at 10:07 ($6), the time delta is 10:07 – 10:02 = 5 minutes)
我提出的解决方案是 O(N2)，有一个小的优化:
for(int i = 0; i < lines.size(); i++){
for(int j = lines.size()-1; j >= 0; j--){
try
{
String[] partsFirst = lines.get(i).split(",");
String[] partsLast = lines.get(j).split(",");
String firstPriceString = partsFirst[1];
String lastPriceString = partsLast[1];
String firstDateString = partsFirst[0];
String lastDateString = partsLast[0];
double firstPriceInt = Double.parseDouble(firstPriceString);
double lastPriceInt = Double.parseDouble(lastPriceString);
Date date1 = format.parse(firstDateString);
Date date2 = format.parse(lastDateString);
long difference = date2.getTime() - date1.getTime();
//optimization
if(difference <= maxDuration)
continue;
if(lastPriceInt > firstPriceInt && (difference) > maxDuration)
maxDuration = difference;
}
catch (ParseException ex)
{
System.out.println("Exception "+ex);
}
}
}
有没有更有效的解决方案？
最佳答案
是的，有一个 O(n) 时间算法。
向前扫描价格(从头到尾)，将低于所有先前价格的价格及其时间存储在辅助数组中。做一些类似的事情来找到大于所有后续价格的所有价格。这些数组自然都是有序的。
最佳交易从第一个数组买入并卖出到第二个数组。两个数组的变体排序合并将识别所有 O(n) 交易，这些交易在一个端点固定的情况下是有利可图的，并且距离最大。
合并的工作方式是，我们将一个索引初始化为“买入”(第一个)数组，将另一个索引初始化为“卖出”(第二个)数组，从最低价格开始。如果当前买入价低于当前卖出价，则考虑该交易并转到下一个最高买入价。否则，转到下一个最高售价。
关于java - 最长的盈利交易算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27551793/