在股票价值数组中寻找买入/卖出价格以最大化正差价

Question

在股票价值数组中寻找买入/卖出价格以最大化正差价

arraysoptimizationcomplexity-theorystocks

20

今天在面试中遇到了这个问题，它的优化解决方案让我感到崩溃（因为我真的很想在这家公司工作...）

给定一个实数数组，每个元素都代表一家公司在任意时间段后的股票价值，找出最佳购买价格及其相应的最佳售出价格（低买高卖）。

举个例子，我们来看 Company Z 的股票代码：

55.39 109.23 48.29 81.59 105.53 94.45 12.24

需要注意的重要事项是该数组在时间上是“排序”的，也就是随着时间的推移，数值会被附加到数组的右端。因此，我们的购买值必须在卖出值的左侧（这是必须的）。

(在上面的示例中，理想解决方案是以48.29的价格购买，以105.53的价格出售。)

我很容易地想到了一个O(n²)复杂度的朴素解决方案(用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)的解决方案，但我完全没能想出来（是的，我知道，失败了）。有人知道如何实现这个线性时间复杂度的解决方案吗？（任何你熟悉的编程语言都可以）谢谢！

编辑

我想对于任何感兴趣的人来说，我今天刚收到消息，我没能得到那份工作，而他们就是在面试时问了我这个问题。 :(

- Magsol

1

我想看一些这方面的功能实现...这让我想起了函数式编程人员在棘手的问题上很好地处理的那种方式... - robince

你在彭博社面试过，对吧？ - Jacob Krall

干得好，不要担心工作，面试很靠运气，真的不能很好地衡量现实世界的表现。 - Brian Ogden

24个回答

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 的更新答案来回答这个问题，并将其适应于您的语言。

- Doug T.

我一直在摸索类似这样的解决方案，就像我一路蹒跚前行一样；我设置了五个变量，就像你一样。不幸的是，我开始做一些疯狂的值交换，然后基本上就走火入魔了。=/ - Magsol

2

我重建了我的算法，现在它和你的一样了...虽然是不同的语言，但有一些非常好的评论，所以我会保留它。 - Austin Salonen

当您交换152.0和170.0时（即当stocks = {10.50，55.39，109.23，48.29，81.59，105.53，94.45，12.24，170.0，2，152.0}时），此方法无法正常工作。 - user6123723

3

这个想法很简单。保持两个指针，lo和hi。
做一个For循环

如果价格比hi高，则更新hi = price，继续
如果价格低于hi。那么lo和hi是可能的候选者之一。计算利润，如果它比以前的利润要大，请存储它并将lo、hi重置为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

就是这样

- dalef

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

- inigo333

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

- shekhar

0

我想描述一下我如何解决这个问题，以便更容易理解我的代码:

（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) + ")");

}

- Sarp Centel

0

Scala解决方案：

示例：[7, 2, 5, 6, 1, 3, 6, 4]

保留一个指向最后一个最低股票价格（lastStockPrice）的指针，并将其与当前股票价格进行比较。当您到达当前股票价格<上一个最小股票价格的点时，更新lastStockPrice。

在循环数组时，跟踪当前价格和lastStockPrice之间的最大差异（利润），因为当您更新lastStockPrice时，利润可能会发生变化。

下面的Scala代码以O（n）时间运行，并占用恒定的空间。

object Solution {
    def maxProfit(prices: Array[Int]): Int = {
        var lastStockPrice = Int.MaxValue
        var maxProfit = 0
        for(currentPrice <- prices){
            if(currentPrice < lastStockPrice){
                lastStockPrice = currentPrice;
            }else if(currentPrice - lastStockPrice > maxProfit){
                maxProfit = currentPrice - lastStockPrice;
            }
        }
        maxProfit
    }
}

- Shilpa

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

- user457660

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

- Sandeep vashisth

0

这是一个 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)

- Evan Burbidge

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Austin Salonen · Accepted Answer

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

编辑: 基于@Joe的失败测试案例，我们有了新的算法 - 很好的发现！这也是与@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);
}