买卖股票的最佳时间  


难度级别 易得奖学金
经常问 土砖 亚马逊 Apple 彭博 ByteDance 思科 易趣 Expedia的 Facebook 高盛 谷歌 JP摩根 微软 摩根士丹利 神谕 贝宝 Qualtrics Samsung VMware的
排列 动态编程

问题陈述  

问题“最佳买卖股票时间”指出您有一个 排列 长度为n的价格,第i个元素存储第i天的股票价格。
如果我们仅能进行一笔交易,即在一天之内买入并在即将到来的另一天卖出,那么所赚取的最大利润将是多少。

使用案列  

prices[] = {7, 1, 5, 3, 6, 4}
5

算法  

如果我们在第i天买入股票,则通过在i +1到n之间的一天卖出股票来赚取最大利润,以使该天具有该股票的最高价格,并且该价格大于price [i]。
考虑价格= {7、1、5、3、6、4}

买卖股票的最佳时间Pin
因此,通过在第2天购买股票并在第5天卖出股票可获得最大利润,而获得的最大利润为5。

最佳时间买卖股票的幼稚方法  

实施上述算法的幼稚方法是运行两个嵌套循环,一个用于购买日,另一个用于在接下来的几天中找到最大利润。

参见
检查数组是否包含允许重复的连续整数

伪代码

int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = price[i];
  int max = -infinity;
  // Finding the maximum stock price greater than costPrice on upcoming days
  for (int j = i + 1; j < n; j++) {
    if (prices[j] > costPrice) {
      max = maximum(max, a[j]);
    }
  }
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

复杂度分析

时间复杂度

O(n ^ 2), 因为我们使用两个嵌套循环来获取当天买卖股票的时间。 因此,时间复杂度是多项式的。

空间复杂度

O(1), 因为我们不存储有关任何数据结构中每个元素的任何信息。 我们一直只使用恒定的空间。 因此,空间复杂度是线性的。
其中n是数组中元素的数量。

最佳买卖股票时间的最佳方法  

更好的方法是形成一个 排列 其第i个元素存储存在于其中的最大值 价格 从索引i +1到n的数组。 也就是说,我们正在以朴素的方式预先计算内部嵌套循环完成的工作。 这样,我们可以通过直接找到最大值来替换内部嵌套循环。 预计算算法以以下方式工作。

  1. 创建一个名为maxSP的数组,其大小等于size 价格 数组和变量max并将其初始化为最小值。
  2. 从中的最后一个索引开始 价格 数组。
    1. 如果价格[i]大于最大值
      1. 将最大值更新为价格[i],并将maxSP [i]设为最小值
    2. 否则,如果价格[i]不大于最大值
      1. 更新maxSP [i] =最大值。
  3. 在进行预计算之后,我们将采用朴素的方法,并使用刚刚创建的maxSP数组替换内部嵌套循环。
参见
数组中最频繁的元素

伪代码

// Pre computation
int max = -infinity;
for (int i = n - 1; i >= 0; i--) {
  if (prices[i] > max) {
    max = prices[i];
    maxSP[i] = -infinity;
  } else {
    maxSP[i] = max;
  }
}
// Do as in naive approach
int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = prices[i];
  // Rather than using a loop to calculate max, we can directly get it from maxSP array
  int max = maxSP[i];
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

代码

最佳买卖股票时间的Java代码

import java.util.Scanner;

class BestTimetoBuyandSellStock {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // Prices array
        int prices[] = new int[]{7, 1, 5, 3, 6, 4};

        // Calculating the max profit
        int ans = maxProfit(prices, prices.length);

        // Print the answer
        System.out.println(ans);
    }

    private static int maxProfit(int[] prices, int n) {
        int maxSP[] = new int[n];
        int max = Integer.MIN_VALUE;

        // Construct the maxSP array
        for (int i = n - 1; i >= 0; i--) {
            if (prices[i] > max) {
                max = prices[i];
                maxSP[i] = Integer.MIN_VALUE;
            } else {
                maxSP[i] = max;
            }
        }

        int profit = 0;
        for (int i = 0; i < n; i++) {
            if (maxSP[i] != Integer.MIN_VALUE) {
                profit = Math.max(profit, maxSP[i] - prices[i]);
            }
        }

        // Return profit
        return profit;
    }
}
5

最佳买卖股票时间的C ++代码

#include <bits/stdc++.h>
using namespace std;

int maxProfit(int *prices, int n) {
    int maxSP[n];
    int max = INT_MIN;
    
    // Construct the maxSP array
    for (int i = n - 1; i >= 0; i--) {
        if (prices[i] > max) {
            max = prices[i];
            maxSP[i] = INT_MIN;
        } else {
            maxSP[i] = max;
        }
    }
    
    int profit = 0;
    for (int i = 0; i < n; i++) {
        if (maxSP[i] != INT_MIN) {
            profit = std::max(profit, maxSP[i] - prices[i]);
        }
    }
    
    // Return profit
    return profit;
}

int main() {
    // Prices array
    int prices[] = {7, 1, 5, 3, 6, 4};
    
    // Calculating the max profit
    int ans = maxProfit(prices, sizeof(prices) / sizeof(prices[0]));
    
    // Print the answer
    cout<<ans<<endl;
    return 0;
}
5

复杂度分析

时间复杂度

上), 因为我们已经在最大利润的预计算和计算过程中遍历了数组的n个元素。 时间复杂度是线性的。

参见
子集总和问题

空间复杂度

上), 因为在预计算部分中,我们在当天之后的第二天存储了最高售价。 由于它是为数组中的所有元素存储的。 空间复杂度也是线性的。
其中n是数组中元素的数量。