121. 买卖股票的最佳时机

image.png

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int low = Integer.MAX_VALUE;
  4.         int result = 0;
  5.         for(int i = 0; i < prices.length;i++){
  6.             low = Math.min(low,prices[i]);
  7.             result = Math.max(result,prices[i] - low);
  8.         }
  9.         return result;
  10.     }
  11. }

动态规划
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solution/bao-li-mei-ju-dong-tai-gui-hua-chai-fen-si-xiang-b/
image.png

  1. public class Solution 
  3.     public int maxProfit(int[] prices) {
  4.         int len = prices.length;
  5.         // 特殊判断
  6.         if (len < 2) {
  7.             return 0;
  8.         }
  9.         int[][] dp = new int[len][2];
  11.         // dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数
  12.         // dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数
  14.         // 初始化：不持股显然为 0，持股就需要减去第 1 天（下标为 0）的股价
  15.         dp[0][0] = 0;
  16.         dp[0][1] = -prices[0];
  18.         // 从第 2 天开始遍历
  19.         for (int i = 1; i < len; i++) {
  20.             dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  21.             dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
  22.         }
  23.         return dp[len - 1][0];
  24.     }
  25. }

122. 买卖股票的最佳时机 II

image.png
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 特殊判断
        if (len < 2) {
            return 0;
        }
        // 0：持有现金
        // 1：持有股票
        // 状态转移：0 → 1 → 0 → 1 → 0 → 1 → 0
        int[][] dp = new int[len][2];
        //如果什么都不做
        dp[0][0] = 0;
        //如果持有股票
        dp[0][1] = -prices[0];

        // 从第 2 天开始遍历
        for (int i = 1; i < len; i++) {
            //i天持有现金，即i-1天持有现金/i-1天持有现金，i天买入股票
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            //同理
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }
}

public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        // cash：持有现金
        // hold：持有股票
        // 状态数组
        // 状态转移：cash → hold → cash → hold → cash → hold → cash
        int[] cash = new int[len];
        int[] hold = new int[len];

        cash[0] = 0;
        hold[0] = -prices[0];

        for (int i = 1; i < len; i++) {
            // 这两行调换顺序也是可以的
            cash[i] = Math.max(cash[i - 1], hold[i - 1] + prices[i]);
            hold[i] = Math.max(hold[i - 1], cash[i - 1] - prices[i]);
        }
        return cash[len - 1];
    }
}

public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        // cash：持有现金
        // hold：持有股票
        // 状态转移：cash → hold → cash → hold → cash → hold → cash

        int cash = 0;
        int hold = -prices[0];

        int preCash = cash;
        int preHold = hold;
        for (int i = 1; i < len; i++) {
            cash = Math.max(preCash, preHold + prices[i]);
            hold = Math.max(preHold, preCash - prices[i]);

            preCash = cash;
            preHold = hold;
        }
        return cash;
    }
}

123. 买卖股票的最佳时机 III

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/solution/javayi-ge-si-lu-da-bao-suo-you-gu-piao-t-pd1p/
image.png

class Solution {
    public int maxProfit(int K, int[] prices) {//这里悄咪咪把小k换成了大K，便于后续索引赋值
        int n=prices.length;
        if(n<=1)    return 0;
        //因为一次交易至少涉及两天，所以如果k大于总天数的一半，就直接取天数一半即可，多余的交易次数是无意义的
        K=Math.min(K,n/2);

        /*dp定义：dp[i][j][k]代表 第i天交易了k次时的最大利润，其中j代表当天是否持有股票，0不持有，1持有*/
        int[][][] dp=new int[n][2][K+1];
        for(int k=0;k<=K;k++){
            dp[0][0][k]=0;
            dp[0][1][k]=-prices[0];
        }

        /*状态方程：
        dp[i][0][k]，当天不持有股票时，看前一天的股票持有情况
        dp[i][1][k]，当天持有股票时，看前一天的股票持有情况*/
        for(int i=1;i<n;i++){
            for(int k=1;k<=K;k++){
                dp[i][0][k]=Math.max(dp[i-1][0][k],dp[i-1][1][k]+prices[i]);
                dp[i][1][k]=Math.max(dp[i-1][1][k],dp[i-1][0][k-1]-prices[i]);
            }
        }
        return dp[n-1][0][K];
    }
}

作者：Destinytomycode
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/solution/javayi-ge-si-lu-da-bao-suo-you-gu-piao-t-pd1p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

309. 最佳买卖股票时机含冷冻期

image.png