Найти цены покупки/продажи в массиве значений запасов, чтобы максимизировать положительную разницу

Ответ 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)