20

今日のインタビューでこの質問を受けましたが、その最適化されたソリューションは私を凍らせました (私は本当にこの会社で働きたかったので...)

それぞれが任意の期間の後の会社の株価を表す実数値の 1 つの配列が与えられた場合、最良の購入価格とそれに対応する最良の売却価格 (安く買って高く売る) を見つけます。

例を挙げて説明するために、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) solutionがあり、それを理解しようとして完全に爆撃しました (ええ、私は知っています、FAIL)。線形時間ソリューションを実装する方法を知っている人はいますか? （慣れ親しんだ言語で構いません）ありがとうございます！

編集

興味のある人のために言うと、今日、彼らが私にこの質問をした場所で面接した仕事に就けなかったという知らせを受け取った. :(

4

24 に答える 24

14

C# の場合:

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);
}

EDIT : @Joe の失敗したテスト ケースに基づく新しいアルゴリズム - ナイス キャッチ BTW! @Doug T's now...と同じ回答でもあります...

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);
}
于 2009-11-02T20:52:50.247 に答える
10

これが試みです（C ++）。基本的に、新しいトップを追跡するたびに、それがこれまでで最高の利益であるかどうかを確認しようとします. 「底」が先に発見されたに違いないことはわかっています。その時点で、トップ、ボトム、現在の最大利益を覚えています。後で新しい底が発見された場合、それは現在の高値の後であるため、上値をリセットして、"上値" をわずかに下げるとより良い利益が得られるかどうかを確認する必要があります。

#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の更新された回答を使用し、それをあなたの言語に適応させることを強くお勧めします。

于 2009-11-02T20:48:50.090 に答える
2 
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

于 2014-06-23T23:33:05.340 に答える
1 
      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);
    }
于 2011-07-06T09:08:01.627 に答える
0

これがJavascriptを使った私の試みです。スクリプトは、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);
于 2012-04-01T09:59:37.417 に答える
0

これは実際に機能する 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]; double potentialProfit = 価格[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 );

}

于 2013-02-20T22:42:23.120 に答える
0

私は同じことで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;
}
于 2014-11-11T11:03:34.430 に答える
0

囲碁を学び、またこれに頭を悩ませようとする私の努力の中で、ここに私の試みがあります。

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]
}
于 2011-12-23T06:43:53.163 に答える
0

これが私の 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 );
}
于 2011-03-24T00:03:27.017 に答える
0

この問題に対して次のアルゴリズムを思いつきました。すべての入力に対して機能するようです。また、Stock の値が下がり続ける場合、プログラムはこの株を買わないように出力します。

  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) です

于 2013-07-19T18:43:07.033 に答える
0

1. 「買い」の後に「売り」が発生する必要があるため、値の最小額を「ベストバイ」、最大額を「ベストセラー」と単純に解釈することはできません。

2.記録された最小値を「ベストバイ」として扱ってはなりません。これは、記録された最小値との差が「記録された利益」よりも少ない可能性がある利益をもたらす可能性がある株価を翌日に持つ可能性があるためです。

3. Best Buy と Best Sell は、これらの値の間の正の差が最大の利益になるため、単一のバリアントとして扱われます。

4.過去に記録された最小値は潜在的な買い候補であるため、記録された最小値と現在の株価に対して最大利益条件を常にチェックする必要があります。の記録された最小値は、理由 2 により「Best Buy」を構成しません。

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;

}

}

于 2013-04-01T13:37:49.897 に答える
0

別の Ruby ソリューション:

# Here's 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's see about the result.
puts "\nbest_buy_time: ", best_buy_time, "\nbest_sell_time: ", best_sell_time, "\nmax_profit: ", max_profit
于 2015-09-16T01:32:27.120 に答える
0

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

乾杯

于 2014-05-14T18:20:57.090 に答える
0

コードを理解しやすくするために、この問題にどのように取り組んだかを説明したいと思います。

(1) 毎日、その日に株を売らなければならないとしたら、それを買うために支払うことができた最低金額はいくらですか? 基本的に、その日の前に最低価格を追跡しています

(2) 毎日、その日に売ったらいくら稼げますか? （当日株価－最低値）

これは、(1) これまでの最低株価 (2) これまでで最高の収益という 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) + ")");

}
于 2011-02-18T10:43:12.547 に答える
0

これはどうですか？

min = 100000000
max = 0

for elem in inp:
    if elem < min:
       min = elem
    tempMax = elem-min
    if tempMax > max:
        max = tempMax

print(max)
于 2015-12-29T16:40:08.300 に答える
0

O(n) はばかげている境界線であるため、あなたがそれを解決することを期待して、インタビューの質問として指摘する必要があります。面接の質問は、あなたが解決できた問題を解決できることを証明するためのものです。O(N^2) 対 O(N) で解決したという事実は関係ありません。O(N) でこれを解決できなかったために会社があなたの採用を見送ったとしても、それはおそらくあなたが働きたいと思っていた会社ではないでしょう。

于 2009-11-02T21:59:53.223 に答える
0

Heresは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)

于 2016-07-06T09:24:29.490 に答える
0

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));
于 2016-05-26T17:21:52.587 に答える