Найти цены покупки/продажи в массиве значений запасов, чтобы максимизировать положительную разницу
Получил этот вопрос в интервью сегодня, и его оптимизированное решение остановило меня холодно (что удары, потому что я действительно хотел работать для этой компании...)
Для одного массива реальных значений, каждый из которых представляет собой стоимость акций компании после произвольного периода времени, найдите лучшую цену покупки и соответствующую ему самую выгодную цену продажи (покупка низкая, высокая продажа).
Чтобы проиллюстрировать пример, позвольте взять биржевой тикер компании 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) решение, и я полностью бомбил, пытаясь понять это (да, я знаю, FAIL). Кто-нибудь знает, как реализовать линейное решение времени? (любой язык, с которым вам удобно) Спасибо!
Изменить
Я полагаю, для всех, кого это интересует, я только что получил сегодня слово, что не получил работу, за которую я взял интервью, где они задали мне этот вопрос.: (
Ответы
Ответ 1
Вот попытка (С++). В основном каждый раз, когда я отслеживаю новый топ, я пытаюсь понять, насколько это выгодно. Я знаю, что "дно" должно быть обнаружено ранее. В этот момент я помню верхнюю, нижнюю и текущую максимальную прибыль. Если позже будет обнаружено новое дно, оно ПОСЛЕ текущей вершины, поэтому мы должны reset top и посмотреть, может ли получить более низкую "верхнюю" верхнюю прибыль.
#include <iostream>
int main()
{
double REALLY_BIG_NO = 1e99;
double bottom = REALLY_BIG_NO; // arbirtrary large number
double currBestBuy = 0.0;
double top = 0.0;
double currBestSell = 0.0;
double profit = 0.0;
// array of prices
double prices[] = {10.50, 55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24, 152.0, 2, 170.0};
int numPrices = 10;// number of prices
for (int i = 0; i < numPrices; ++i)
{
if (prices[i] < bottom)
{
bottom = prices[i];
// reset the search on a new bottom
top = 0.0;
}
else if (prices[i] > top)
{
top = prices[i];
// calculate profit
double potentialProfit = (top - bottom);
if (potentialProfit > profit &&
bottom != REALLY_BIG_NO)
{
profit = potentialProfit;
currBestSell = top;
currBestBuy = bottom;
}
}
}
std::cout << "Best Buy: " << currBestBuy << "Best Sell: " << currBestSell << std::endl;
}
До сих пор я играл с кучей разных наборов ввода, и до сих пор у меня не было никаких проблем... (дайте мне знать, если вы проверите это и увидите что-то не так)
Я настоятельно рекомендую использовать обновленный ответ Austin Salonen на этот вопрос и адаптировать его к вашему языку.
Ответ 2
В С#:
static void Main(string[] args)
{
double[] values = new double[7]{55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};
double max = double.MinValue, maxDiff = double.MinValue, diff = 0;
for (int i = 1; i < values.Length; i++)
{
if (values[i] > values[i - 1])
{
//trending upward, append to existing differential
diff += values[i] - values[i - 1];
}
else
{
//trending downward, reset the diff
diff = 0;
}
if (diff > maxDiff)
{
maxDiff = diff;
max = values[i];
}
}
Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}
РЕДАКТИРОВАТЬ: Новый алгоритм, основанный на тестовом примере с ошибкой @Joe - Nice Catch BTW! Это также тот же ответ, что и @Doug T...
static void Main(string[] args)
{
double[] values = new double[8] { 55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24 };
double max = double.MinValue, maxDiff = double.MinValue, diff = 0;
double bottom = values[0];
for (int i = 1; i < values.Length; i++)
{
diff += values[i] - values[i - 1];
if (diff > maxDiff)
{
maxDiff = diff;
max = values[i];
}
if (values[i] < bottom)
{
bottom = values[i];
diff = 0;
}
}
Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}
Ответ 3
Идея проста. Держите два указателя, lo и hi.
Сделайте петлю Foor
- если цена выше hi, обновите hi = цена, продолжите
- если цена ниже hi. Тогда lo и hi - один из возможных кандидатов. Рассчитайте прибыль, сохраните ее, если она будет больше, чем предыдущая прибыль, и reset lo, hi to price
def getBestProfit(prices):
lo = hi = profit = 0
for price in prices:
if lo == 0 and hi == 0:
lo = hi = price
if price > hi:
hi = price
if price < low:
tmpProfit = hi - lo
if tmpProfit > profit:
profit = tmpProfit
lo = hi = price
return profit
Что он
Ответ 4
void getBestTime (int stocks[], int sz, int &buy, int &sell){
int min = 0;
int maxDiff = 0;
buy = sell = 0;
for (int i = 0; i < sz; i++)
{
if (stocks[i] < stocks[min])
{
min = i;
}
int diff = stocks[i] - stocks[min];
if (diff > maxDiff)
{
buy = min;
sell = i;
maxDiff = diff;
}
}}
На всякий случай вы предпочитаете этот ответ. Я нашел его в другой сети, но все же.
источник: http://leetcode.com/2010/11/best-time-to-buy-and-sell-stock.html
Ответ 5
public void profit(float stock[], int arlen ){
float buy = stock[0];
float sell = stock[arlen-1];
int bi = 0;
int si = arlen - 1;
for( int i = 0; i < arlen && bi < si ; i++){
if( stock[i] < buy && i < si){
buy = stock[i];
bi = i;
}
if(stock[arlen - i - 1] > sell && (arlen - i -1) > bi){
sell = stock[arlen - i - 1];
si = arlen - i - 1;
}
}
System.out.println(buy+" "+sell);
}
Ответ 6
Мне действительно нужно указать в качестве вопроса интервью, в котором вы решите его решить, так как O (n) является абсурдным. Интервью вопросы предназначены, чтобы доказать, что вы можете решить проблему, которую вы смогли решить. Тот факт, что вы решили его в O (N ^ 2) и O (N), не должен иметь значения. Если компания перейдет на то, чтобы нанять вас за то, что вы не решили это в O (N), возможно, это не компания, в которой вы хотели бы работать.
Ответ 7
Я хотел бы описать, как я подошел к этой проблеме, чтобы было легче понять мой код:
(1) В течение каждого дня, если бы мне пришлось продать мои акции в этот день, какова была бы минимальная сумма, которую я мог бы заплатить, чтобы купить ее? По сути, я отслеживаю минимальную цену до этого дня.
(2) На каждый день, если я буду продавать в тот день, сколько я зарабатываю? (Цена акций в этот день - минимальная цена)
Это показывает, что я должен отслеживать две вещи: (1) минимальная цена акций до сих пор (2), которые лучше всего зарабатывают до сих пор.
Проблема заключается в выборе того, какой день продать. Я буду продавать в тот день, который даст мне лучший заработок. Вот мой код Java:
public static void findBestDeal(double [] stocks) {
double minsofar = stocks[0];
double bestsofar = 0.0;
for(int i=1; i< stocks.length; i++) {
// What is the cheapest price to buy it if I'm going to sell it today
if(stocks[i-1] < minsofar) {
minsofar = stocks[i-1];
}
// How much do I earn if I sell it on ith day?
double current_deal = stocks[i] - minsofar;
// Is selling today better?
if(current_deal > bestsofar) {
bestsofar = current_deal;
}
}
System.out.println("Found the best deal: " + bestsofar + " (Bought at " + minsofar + " and sold at " + (minsofar+bestsofar) + ")");
}
Ответ 8
Вот моя реализация O (n) для этого. Я использую массив изменений для вычисления максимальной прибыли и даты покупки и продажи.
Ваши комментарии по этому поводу приветствуются.
#include<stdafx.h>
#include<stdio.h>
int main()
{
//int arr[10] = {15, 3, 5,9,10,1,6,4,7,2};
int arr[7] = {55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};
int change[7];
int n=7;
for(int i=1;i<=n;i++)
{
change[i] = arr[i]- arr[i-1];
}
int i=0,index = 0;
int sum = 0;
int maxsum = 0;
int startpos = 0;
int endpos = 0;
while(index < n)
{
sum = sum + change[index];
if(maxsum < sum)
{
maxsum = sum;
startpos = i;
endpos = index;
}
else if (sum<0) // negative number ,set sum to zero
{
sum = 0;
i=index+1;
}
index++;
}
printf("max profit is%d %d %d", maxsum , startpos, endpos+1 );
}
Ответ 9
В моих усилиях по изучению Go, а также для того, чтобы разбить мой мозг на этом, вот моя попытка.
func GetMaxProfit2(prices []float64) (float64, float64) {
var min, max, pmin, pmax int
for i, v := range prices {
if v - prices[min] > prices[max] - prices[min] {
pmax = max
max = i
}
// Reset the max when min is updated.
if v < prices[min] {
pmin = min
min = i
pmax = max
max = i
}
}
// If min is ahead of max, reset the values back
if min >= max {
min = pmin
max = pmax
}
return prices[min], prices[max]
}
Ответ 10
Вот моя попытка использования Javascript. script вычисляет ответ в O (N):
//Main Stock Array
var stock = [15, 20, 0, 3, 30, 45, 67, 92, 1, 4, 99];
//Setup initial variable state
var ans = {}, tmp = {}; //These are just for namespacing / syntatic sugar
ans.minVal = stock[0];
ans.minInd = 0;
ans.maxDiff = stock[1] - stock[0];
ans.maxInd = 1;
tmp.minInd = ans.minInd;
tmp.minVal = ans.minVal;
//Basically we iterate throught the array. If we find a new low, we start tracking it. Otherwise we compare the current index against the previously found low
for(i = 1; i <= stock.length-1; i++) {
if(tmp.minVal > stock[i]) {
tmp.minVal = stock[i];
tmp.minInd = i;
} else {
ans.diff = stock[i] - stock[tmp.minInd];
if(ans.diff > ans.maxDiff) { //Looks like we found a new maxDifference. Lets log the indexes
ans.maxDiff = ans.diff;
ans.maxInd = i;
ans.minInd = tmp.minInd;
ans.minVal = tmp.minVal;
}
}
}
document.write('You should buy your stocks on day ' + ans.minInd + ' and sell on day ' + ans.maxInd);
Ответ 11
Это C-решение, которое действительно работает:
void bestBuySell()
{ двойные цены [] = {10.50, 10.0, 3.0, 194.0, 55.39, 2.0, 109.23, 48.29, 81.59, 105.53, 94.45, 191.0, 200.0, 12.24}; int arrSize = 14; double bestBuy = цены [0], bestSell = цены [1], bestPotentialBuy = цены [0]; двойной потенциалProfit = цены [1] - цены [0];
for(int i = 1; i < (arrSize-1); i++)
{
if(prices[i] < bestBuy)
bestPotentialBuy = prices[i];
if((prices[i+1] - bestPotentialBuy) > potentialProfit)
{
bestBuy = bestPotentialBuy;
bestSell = prices[i+1];
potentialProfit = prices[i+1] - bestPotentialBuy;
}
}
printf( "bestBuy %f bestSell %f\n", bestBuy, bestSell );
}
Ответ 12
1. Мы не можем просто взять наименьшую сумму среди значений как "Лучшая покупка" и максимальная сумма как "Лучшая продажа", потому что "Продать" должно произойти после "Купить".
2. Мы не должны рассматривать записанный минимум как "Лучшую покупку", потому что последующие дни могут иметь значения акций, разница которых с зарегистрированным минимумом может приносить прибыль, которая может быть меньше "зафиксированной прибыли".
3.Best Buy и Best Sell рассматриваются как один вариант, потому что это положительная разница между этими значениями, которая делает максимальную прибыль.
4. Поскольку любой зарегистрированный минимум в прошлом является потенциальным кандидатом на покупку, максимальное условие прибыли всегда должно быть проверено на основе зарегистрированного минимума и текущей цены акций. Поэтому нам всегда нужно отслеживать записанный минимум, но просто наличие зарегистрированного минимума не является "Лучшей покупкой" из-за причины № 2.
Теперь имеет смысл использовать код ниже, который выполняется в O (n) раз.
public class BestStockBuyAndSell {
public static void main(String[] args) {
double[] stockPrices = {55.39,109.23,48.29,81.59,105.53,94.45,12.24};
int [] bestBuySellIndex = maxProfit(stockPrices);
System.out.println("Best Buy At "+stockPrices[bestBuySellIndex[0]]);
System.out.println("Best Sell At "+stockPrices[bestBuySellIndex[1]]);
System.out.println("Max Profit = "+(stockPrices[bestBuySellIndex[1]]-stockPrices[bestBuySellIndex[0]]));
}
public static int[] maxProfit(double[] stockPrices)
{
int bestBuy=0;
int bestSell=0;
int[] bestCombination ={bestBuy,bestSell};
double recordedMinimum = stockPrices[bestBuy];
int recordedMinimuIndex = bestBuy;
double bestProfitSofar = stockPrices[bestSell] - stockPrices[bestBuy];
for(int i=1;i<stockPrices.length;i++)
{
if(stockPrices[i] - recordedMinimum > bestProfitSofar)
{
bestProfitSofar = stockPrices[i] - recordedMinimum;
bestSell = i;
bestBuy = recordedMinimuIndex;
}
if(stockPrices[i] < recordedMinimum)
{
recordedMinimuIndex = i;
recordedMinimum = stockPrices[i];
}
}
bestCombination[0] = bestBuy;
bestCombination[1] = bestSell;
return bestCombination;
}
}
Ответ 13
Я придумал следующий алгоритм для этой проблемы, кажется, работает для всех входов. Кроме того, если стоимость акций продолжает расти, программа выйдет не для покупки этого запаса:
public class GetMaxProfit
{
double minValue = -1, maxValue = -1;
double maxDiff = 0;
public void getProfit(double [] inputArray){
int i=0, j=1;
double newDiff = 0;
while(j<inputArray.length){
newDiff = inputArray[j]-inputArray[i];
if(newDiff > 0){
if(newDiff > this.maxDiff){
this.minValue = inputArray[i];
this.maxValue = inputArray[j];
this.maxDiff = newDiff;
}
}
else{
i = j;
}
j++;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
GetMaxProfit obj = new GetMaxProfit();
obj.getProfit(new double[]{55.39, 19.23, 14.29, 11.59, 10.53, 9.45, 1.24});
if(obj.minValue != -1 && obj.maxValue != -1){
System.out.println("Buy Value for the input: "+obj.minValue);
System.out.println("Sell Value for the input: "+obj.maxValue);
System.out.println("Best profit for the input: "+obj.maxDiff);
}
else
System.out.println("Do Not Buy This STOCK!!);
}
}
Есть ли какие-либо уловки, которые вы могли бы найти в этом? Это временная сложность O (N)
Ответ 14
Вот мое решение, такое же, как @Doug T., кроме того, что я отслеживаю день в индексе. Пожалуйста, предоставьте отзыв.
int prices[] = {4,4,5,6,2,5,1,1};
//int prices[] = {100, 180, 260, 310, 40, 535, 695};
int currentBestSellPrice=0;
int currentBestBuyPrice=0;
int lowindex=0;
int highindex=0;
int low=prices[0];
int high=prices[0];
int profit=0;
int templowindex=0;
for(int i=0; i< prices.length;i++)
{
// buy low
if(prices[i] < low && i+1 < prices.length)
{
low = prices[i];
templowindex=i;
high=0;
}
// sell high
else if(prices[i] > high)
{
high = prices[i];
int potentialprofit = (high-low);
if(potentialprofit > profit)
{
profit = potentialprofit;
currentBestSellPrice = high;
currentBestBuyPrice = low;
highindex=i;
lowindex=templowindex;
}
}
}
System.out.println("Best Buy Price : "+ currentBestBuyPrice + " on day "+ lowindex);
System.out.println("Best Sell Price : "+ currentBestSellPrice+ " on day "+ highindex );
Ответ 15
Решение F # для тех, кто интересуется функционалом, принимает на себя это. Я бы не сказал, хотя это сильно отличается.
let start, _, profit =
[55.39; 109.23; 48.29; 81.59; 81.58; 105.53; 94.45; 12.24 ]
|> Seq.fold (fun (start,newStart,profit) i ->
let start = defaultArg start i
let newStart = defaultArg newStart i
let newProfit = i - newStart
if profit < newProfit
then Some newStart, Some newStart,newProfit
else if start > i
then Some start, Some i, profit
else Some start,Some newStart,profit) (None,None, 0.0)
printf "Best buy: %f; Best sell: %f" start.Value (start.Value + profit)
Вывод:
Best buy: 48.290000; Best sell: 105.530000
Ответ 16
Вот мое решение в Ruby:
values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]
max_diff = 0
diff = 0
min = values[0]
max = 0
values.each_with_index do |value, index = 1|
# get an array of the previous values before the current one
lag_values = values[0..index]
# get the minimum of those previous values
min_lag_value = lag_values.min
# difference between current value and minimum of previous ones
diff = values[index].to_i - min_lag_value.to_i
# if current difference is > previous max difference, then set new values for min, max_diff, and max
if diff > max_diff
max_diff = diff
min = min_lag_value
max = values[index]
end
end
min # => 48.29
max # => 105.3
max_diff # => 57
Приветствия
Ответ 17
Я получил 100% за то же самое, здесь вы идете.
public int solution(int[] A) {
if (A == null || A.length<=1){
return 0;
}
int minValue = Math.min(A[0], A[1]);
int profit = A[1] - A[0];
for (int i = 2; i < A.length; i++) {
minValue = Math.min(minValue, A[i]);
profit = Math.max(A[i] - minValue,profit);
}
return profit > 0 ? profit : 0;
}
Ответ 18
Как я думал об этом, для каждого индекса i
, какой будет идеальный индекс для продажи этого запаса? Это, конечно, индекс максимального значения после i
. Это уменьшает нашу проблему до нахождения максимального элемента после индекса i
для каждого i
в [1 ... n]
. Если бы мы могли это сделать в O(n)
времени, тогда мы могли бы найти лучший выбор среди них и сообщить об этом.
Способ сделать это - начать перемещение с конца массива, поддерживая две переменные, один из которых сохранит самый большой элемент, с которым мы столкнулись до сих пор max_till_now
, и один, чтобы сохранить максимальную прибыль, которую мы могли бы получить до сих пор, profit
. Это просто так, что мы можем сделать это за один проход. Мы могли бы также использовать дополнительное пространство и для каждого элемента i
, сохранить индекс наибольшего элемента в диапазоне [i + 1 ... n]
для него, а затем найти максимальную прибыль.
Здесь мой код python:
def buyLowSellHigh(L):
length = len(L)
profit = 0
max_till_now = L[length - 1]
for i in xrange(length - 2, -1, -1):
if L[i] > max_till_now: max_till_now = L[i]
else:
if max_till_now - L[i] > profit: profit = max_till_now - L[i]
return profit
Ответ 19
Другое решение Ruby:
# Here some examples. Please feel free to give your new test.
values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]
# values = [5, 6, 4, 7, 9, 8, 8]
# values = [5, 10, 4, 6, 7]
# values = [5, 10, 4, 6, 12]
# values = [1, 2, 3, 4, 5]
# Initialize parameters.
min = values[0]
best_buy_time = values[0]
best_sell_time = values[0]
max_profit = 0
# This solution is based on comparing previous k elements and k+1 one.
# The runtime is O(n) and it only use O(1) auxiliary storage.
values.each_with_index do |value, index = 1|
# Check value in this turn.
puts value
# Check current value is bigger than min or not.
# If not, we find the new min.
if value <= min
min = value
# If current value is bigger than min and
# (value - min) is bigger than previous max_profit,
# set new best_buy_time, best_sell_time & max_profit.
else
if value - min >= max_profit
best_buy_time = min
best_sell_time = value
max_profit = value - min
end
end
end
# Let see about the result.
puts "\nbest_buy_time: ", best_buy_time, "\nbest_sell_time: ", best_sell_time, "\nmax_profit: ", max_profit
Ответ 20
как насчет этого?
min = 100000000
max = 0
for elem in inp:
if elem < min:
min = elem
tempMax = elem-min
if tempMax > max:
max = tempMax
print(max)
Ответ 21
Решение в javascript
var stockArr = [13931, 9889, 987, 4, 89, 100];
function getBestTime(sortedArr) {
var min = 0;
var buyIndx = 0;
var saleIndx = 0;
var maxDiff = 0;
for (var i = 0; i < stockArr.length; i++) {
if (stockArr[i] < stockArr[min]) {
min = i;
}
var diff = stockArr[i] - stockArr[min];
if (diff > maxDiff) {
buy = min;
sale = i;
maxDiff = diff;
}
}
return {
buy:buy+1,
sale:sale+1,
diff:maxDiff
}
}
console.log(getBestTime(stockArr));
Ответ 22
Вот решение javascript.
function getMax(arr){
//we need more than at least 3 ints to be able to do this
if(arr.length <= 1) return arr;
// get the minimum price we can sell at to make a profit
var min = arr[0];
//get the first potential maximum profit
var max = arr[1] - arr[0];
//while looping through we must get a potential value,
//we can then compare that using the math.max using the maximum
//and the potential prices that we have seen. Once the loop runs the ouput here should be 6!
for(var i = 1; i < arr.length; ++i){
var current = arr[i];
var potential = current - min;
max = Math.max(max, potential);
min = Math.min(min, current);
}
return max;
}
console.log(getMax([10, 7, 5, 8, 11, 9]));
Время выполнения на этом O (n)