牛客题

题目：假设你有一个数组，其中第i 个元素是股票在第i 天的价格。 你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益

示例：

输入：
[1,4,2]
返回值：
3

分析：

• 法1：暴力递归

  • 后面的数>前面的数，记录它们差值中的最大值，就是股票交易的最大利润

public int maxProfit1(int[] prices) {
      if (prices.length == 0) {
          return 0;
      }
      int max = 0;
      for (int i = 0; i < prices.length - 1; i++) {
          for (int j = i + 1; j < prices.length; j++) {
              // 卖出价格>买入价格,才能算收益
              // 这里就会发现一个规律:从后往前找最小值作为买入的价格
              if (prices[j] > prices[i]) {
                  max = Math.max(max, prices[j] - prices[i]);
              }
          }
      }
      return max;
  }

• 法2：暴力递归推出另一个解，记录买入最小值

  • 假设prices[0] 为最小买入价格，后面遍历遇到<它的才更新它

  • 遍历数组，最大利润=当前元素值-目前遇到过最小值，记录最大利润最大值既是答案

// 暴力递归推出另一种解法：从后往前找最小买入价格
public int maxProfit2(int[] prices) {
    if (prices.length == 0) {
        return 0;
    }
    int minPrice = prices[0];
    int maxProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        // 数组中的最小值就是最佳的买入时机
        minPrice = Math.min(minPrice, prices[i]);
        // 最大利润就是当天卖出的价格-最佳买入时间中的最大值
        maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    }
    return maxProfit;
}

• 法3：暴力递归推出动态规划

  • 初始化：dp[i] 记录第i+1 天的最大利润，所以初始化dp[0]=0 ；minPrice记录第i+1天内最小买入价格，所以初始化 minPrice=0

  • 转移方程：

    • 最小买入价 = 从[0...i]中的最小值

    • 当天最大利润 = (前一天最大利润 )or (当前卖出价-目前买入最小价格)中的最大值

  • 返回值：dp[n-1]就是第n天的最大利润

// 将上面方法改成动态规划
public int maxProfit3(int[] prices) {
    if (prices.length == 0) {
        return 0;
    }
    int n = prices.length;
    // dp[i]记录来到第i+1天的最大利润
    int[] dp = new int[n];
    dp[0] = 0;
    int minPrice = prices[0];
    for (int i = 1; i < prices.length; i++) {
        minPrice = Math.min(minPrice, prices[i]);
        // 第i+1天的最大利润：第i天的最大利润，今天卖出-最佳买入时机中的最大值
        dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);
    }
    return dp[n - 1];
}

• 法4：另一种写法的动态规划

  • 初始化：二维数组dp，记录两种状态：第一列表示持有股票，第二列表示没持有股票

  • 转移方程：

    • 第i+1天未持有股票的最大利润：max(第i天未持有的最大利润，第i天持有的利润+今天卖出的价格)

    • 第i+1天持有股票的最大利润：(第i天持有的最大利润，今天买入股票的支出)

  • 返回值：最大利润=最后一天未持有股票的最大利润(因为都卖出去了)

// 另一种动态规划：设两种状态，未持有股票和持有股票
public int maxProfit4(int[] prices) {
    if (prices.length == 0) {
        return 0;
    }
    // dp[i][0]表示第i+1天没持有股票的利润最大值
    // dp[i][1]表示第i+1天持有股票的利润最大值
    int n = prices.length;
    int[][] dp = new int[n][2];
    dp[0][0] = 0;// 第一天没持有股票最大值0
    dp[0][1] = -prices[0];// 第一天持有股票最大值-prices[0].因为第一天只能买股票=花出去
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            // 第i+1天未持有股票的最大利润：max(第i天未持有的最大利润，第i天持有的利润+今天卖出的价格)
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 第i+1天持有股票的最大利润：(第i天持有的最大利润，今天买入股票的支出)
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
    }
    // 最大利润=最后一天未持有股票的最大利润(因为都卖出去了)
    return dp[n - 1][0];
}

// 将上面动态规划改成不需要dp数组
public int maxProfit5(int[] prices) {
    if (prices.length == 0) {
        return 0;
    }
    int noHold = 0;// 第1天未持有股票的利润最大值
    int hold = -prices[0];// 第1天持有股票的利润最大值
    for (int i = 1; i < prices.length; i++) {
        // 第i+1天未持有股票的最大利润：max(第i天未持有的最大利润，第i天持有的利润+今天卖出的价格)
        noHold = Math.max(noHold, hold + prices[i]);
        // 第i+1天持有股票的最大利润：(第i天持有的最大利润，今天买入股票的支出)
        hold = Math.max(hold, -prices[i]);
    }
    // 最大利润=最后一天未持有股票的最大利润(因为都卖出去了)
    return noHold;
}