logo标签列表

最大单笔销售利润

arraysalgorithmbig-otime-complexity
131

假设我们有一个包含n个整数的数组，表示单日股票价格。 我们想要找到一对（买入日，卖出日），其中 buyDay ≤ sellDay，并且如果我们在buyDay购买股票并在sellDay卖出，我们将最大化我们的利润。

显然，通过尝试所有可能的(buyDay，sellDay)对并从中选择最好的，可以得到O(n^2)时间复杂度的算法解决方案。 但是，是否存在更好的算法，例如运行时间为O（n）？

2
这是具有间接层级的最大子序列和问题。 - MSN
2
@MSN：怎么回事？他根本没有看总和，而是在关注元素之间的差异。 - PengOne
2
@PengOne，就像我说的那样，它有一级间接性。具体来说，您想要最大化连续几天的收益/损失总和。因此，将列表转换为收益/损失，并找到最大子序列和。 - MSN
为什么你不能找到最小值和最大值然后返回它们呢？我对这个问题有什么误解吗？ - PDN
1
@PDN：那不行，因为最小值可以出现在最大值之前。你不能卖出股票（在这种情况下），然后再买回来。 - Ajeet Ganga
显示剩余2条评论
20个回答
0
一个简洁的解决方案：
+ (int)maxProfit:(NSArray *)prices {
    int maxProfit = 0;

    int bestBuy = 0;
    int bestSell = 0;
    int currentBestBuy = 0;

    for (int i= 1; i < prices.count; i++) {
        int todayPrice = [prices[i] intValue];
        int bestBuyPrice = [prices[currentBestBuy] intValue];
        if (todayPrice < bestBuyPrice) {
            currentBestBuy = i;
            bestBuyPrice = todayPrice;
        }

        if (maxProfit < (todayPrice - bestBuyPrice)) {
            bestSell = i;
            bestBuy = currentBestBuy;
            maxProfit = (todayPrice - bestBuyPrice);
        }
    }

    NSLog(@"Buy Day : %d", bestBuy);
    NSLog(@"Sell Day : %d", bestSell);

    return maxProfit;
}
0
static void findmaxprofit(int[] stockvalues){
    int buy=0,sell=0,buyingpoint=0,sellingpoint=0,profit=0,currentprofit=0;
    int finalbuy=0,finalsell=0;
    if(stockvalues.length!=0){
        buy=stockvalues[0];
    }           
    for(int i=1;i<stockvalues.length;i++){  
        if(stockvalues[i]<buy&&i!=stockvalues.length-1){                
            buy=stockvalues[i];
            buyingpoint=i;
        }               
        else if(stockvalues[i]>buy){                
            sell=stockvalues[i];
            sellingpoint=i;
        }
        currentprofit=sell-buy;         
        if(profit<currentprofit&&sellingpoint>buyingpoint){             
            finalbuy=buy;
            finalsell=sell;
            profit=currentprofit;
        }

    }
    if(profit>0)
    System.out.println("Buy shares at "+finalbuy+" INR and Sell Shares "+finalsell+" INR and Profit of "+profit+" INR");
    else
        System.out.println("Don't do Share transacations today");
}
0
def get_max_profit(stock):
    p=stock[0]
    max_profit=0
    maxp=p
    minp=p
    for i in range(1,len(stock)):
        p=min(p,stock[i])
        profit=stock[i]-p
        if profit>max_profit:
            maxp=stock[i]
            minp=p
            max_profit=profit
    return minp,maxp,max_profit



stock_prices = [310,315,275,295,260,270,290,230,255,250]
print(get_max_profit(stock_prices))

这个Python3程序可以返回买入和卖出价格，以最大化利润，计算的时间复杂度为O（n），空间复杂度为O（1）。
0
这是我的解决方案。
public static int maxProfit(List<Integer> in) {
    int min = in.get(0), max = 0;
    for(int i=0; i<in.size()-1;i++){

        min=Math.min(min, in.get(i));

        max = Math.max(in.get(i) - min, max);
     }

     return max;
 }
}
0
唯一真正回答这个问题的是@akash_magoon的答案（而且如此简单！），但它没有返回问题中指定的确切对象。我进行了一些重构，并在PHP中给出了我的答案，只返回所要求的内容：
function maximizeProfit(array $dailyPrices)
{
    $buyDay = $sellDay = $cheaperDay = $profit = 0;

    for ($today = 0; $today < count($dailyPrices); $today++) {
        if ($dailyPrices[$today] < $dailyPrices[$cheaperDay]) {
            $cheaperDay = $today;
        } elseif ($dailyPrices[$today] - $dailyPrices[$cheaperDay] > $profit) {
            $buyDay  = $cheaperDay;
            $sellDay = $today;
            $profit   = $dailyPrices[$today] - $dailyPrices[$cheaperDay];
        }
    }
    return [$buyDay, $sellDay];
}
0

这是数组中两个元素之间的最大差异，这是我的解决方案：

O(N) 时间复杂度 O(1) 空间复杂度

    int[] arr   =   {5, 4, 6 ,7 ,6 ,3 ,2, 5};

    int start   =   0;
    int end     =   0;
    int max     =   0;
    for(int i=1; i<arr.length; i++){
        int currMax =   arr[i] - arr[i-1];
        if(currMax>0){
            if((arr[i] -arr[start])>=currMax && ((arr[i] -arr[start])>=(arr[end] -arr[start]))){

                 end    =   i;
            }
            else if(currMax>(arr[i] -arr[start]) && currMax >(arr[end] - arr[start])){
                start   =   i-1;
                end =   i;
            }
        }
    }
    max =   arr[end] - arr[start];
    System.out.println("max: "+max+" start: "+start+" end: "+end);
0

在一次面试Facebook解决方案工程师职位的现场编码考试中失败后，我必须在一个冷静的氛围中解决它，这是我的两分钱意见：

var max_profit = 0;
var stockPrices = [23,40,21,67,1,50,22,38,2,62];

var currentBestBuy = 0; 
var currentBestSell = 0;
var min = 0;

for(var i = 0;i < (stockPrices.length - 1) ; i++){
    if(( stockPrices[i + 1] - stockPrices[currentBestBuy] > max_profit) ){
        max_profit = stockPrices[i + 1] - stockPrices[currentBestBuy];
        currentBestSell = i + 1;  
    }
    if(stockPrices[i] < stockPrices[currentBestBuy]){
            min = i;
        }
    if( max_profit < stockPrices[i + 1] - stockPrices[min] ){
        max_profit = stockPrices[i + 1] - stockPrices[min];
        currentBestSell = i + 1;
        currentBestBuy = min;
    }
}

console.log(currentBestBuy);
console.log(currentBestSell);
console.log(max_profit);
1
不鼓励只回答代码的答案。 - Pritam Banerjee
0

对于多次买入/卖出，请使用以下代码

  • 时间复杂度 O(n)

    n=int(input())
a = list(map(int,input().split())) 
m=0
b=a[0]
s=0
for i in range(1,n):
  if(a[i]<a[i-1]):
    s=a[i-1]
    m=m+s-b
    b=a[i]
if(a[n-1]>b):
  m=m+a[n-1]-b
print(m)
0
一种确定最大利润的可能性是在数组中的每个索引处跟踪左侧最小元素和右侧最大元素。然后，当您遍历股票价格时，对于任何给定的日期，您将知道该日期之前的最低价格，并且您还将知道该日期后（包括该日期）的最高价格。
例如，让我们定义一个名为“min_arr”和“max_arr”的数组，给定数组为“arr”。在“min_arr”中的索引“i”将是所有索引“<= i”（i及其左侧）的“arr”的最小元素。“max_arr”中的索引“i”将是所有索引“>= i”（i及其右侧）的“arr”的最大元素。然后，您可以找到“max_arr”和“min_arr”中相应元素之间的最大差异：
def max_profit(arr)
   min_arr = []
   min_el = arr.first
   arr.each do |el|
       if el < min_el
           min_el = el
           min_arr << min_el
       else
           min_arr << min_el
       end
   end

   max_arr = []
   max_el = arr.last
   arr.reverse.each do |el|
       if el > max_el
           max_el = el
           max_arr.unshift(max_el)
       else
           max_arr.unshift(max_el)
       end

   end

   max_difference = max_arr.first - min_arr.first
   1.upto(arr.length-1) do |i|
        max_difference = max_arr[i] - min_arr[i] if max_difference < max_arr[i] - min_arr[i]  
   end

   return max_difference 
end

这段代码应该以O(n)的时间运行，但我认为它会使用大量的空间。

-1

对于所有跟踪最小和最大元素的答案，该解决方案实际上是一个O(n^2)的解决方案。这是因为最后必须检查最大值是否出现在最小值之后。如果没有，就需要进一步迭代，直到满足该条件，这将导致最坏情况为O(n^2)。如果您想跳过额外的迭代，则需要更多的空间。无论哪种方式，与动态编程解决方案相比都不可取。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接