LeetCode股票买卖系列问题

LeetCode 是一个非常棒的 OJ（Online Judge）平台，收集了许多公司的面试题目。这篇文章主要介绍了如果通过巧妙的方法以及使用动态规范的思想去解决一系列的股票买卖问题

买卖股票的最佳时机

记录 今天之前买入的最小值，

计算 今天之前最小值买入，今天卖出的获利，也即 今天卖出的最大获利，

比较 每天的最大获利，取最大值即可。

class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, max = 0;
        for (int i = 0; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            max = Math.max(max, prices[i] - min);
        }
        return max;
    }
}

买卖股票的最佳时机 II

贪心算法，只要今天价格小于明天价格就在今天买入然后明天卖出。

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - prices[i - 1] > 0) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
}

动态规划，第i天只有两种状态，不持有或持有股票。当天不持有股票的状态可能来自昨天卖出或者昨天也不持有。

同理，当天持有股票的状态可能来自昨天买入或者昨天也持有中，取最后一天的不持有股票状态就是问题的解。

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        // dp[i][0]表示第i天不持有股票, dp[i][1]表示第i天持有股票
        dp[0][1] = - prices[0];
        for (int i = 1; i < len; 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];
    }
}

买卖股票的最佳时机 III

对于任意一天考虑四个变量:

fstBuy: 在该天第一次买入股票可获得的最大收益

fstSell: 在该天第一次卖出股票可获得的最大收益

secBuy: 在该天第二次买入股票可获得的最大收益

secSell: 在该天第二次卖出股票可获得的最大收益

分别对四个变量进行相应的更新, 最后secSell就是最大收益值

class Solution {
    public int maxProfit(int[] prices) {
        int fstBuy = Integer.MIN_VALUE, fstSell = 0;
        int secBuy = Integer.MIN_VALUE, secSell = 0;
        for (int p : prices) {
            fstBuy = Math.max(fstBuy, -p);
            fstSell = Math.max(fstSell, fstBuy + p);
            secBuy = Math.max(secBuy, fstSell - p);
            secSell = Math.max(secSell, secBuy + p); 
        }
        return secSell;
    }
}

left[i] = max(left[i - 1], prices[i] - min) 从前往后遍历，表示第1天到第i天之间的最大利润（通过是否在第i天卖出确认）

right[i] = max(right[i + 1], max - prices[i]) 从后往前遍历，表示第i天到最后一天之间的最大利润（通过是否在第i天买进确认）

res = max(left + right)，(dp1 + dp2)[i] 正好表示从第1天到最后一天经过两次交易的最大利润

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0)
            return 0;
        int len = prices.length, ret = 0;
        int[] left = new int[len + 1], right = new int[len + 1];
        int profit = 0, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;;
        for (int i = 1; i <= len; i++) {
            min = Math.min(min, prices[i - 1]);
            left[i] = Math.max(left[i - 1], prices[i - 1] - min);
        }
        profit = 0;
        for (int i = len - 1; i >= 0; i--) {
            max = Math.max(max, prices[i]);
            right[i] = Math.max(right[i + 1], max - prices[i]);
        }
        for (int i = 0; i < len; i++) {
            ret = Math.max(left[i + 1] + right[i], ret);
        }
        return ret;
    }
}

买卖股票的最佳时机 IV

动态规划

  • 状态穷举：
  • dp[i][k][1] 标识第i天交易了k次手里持有股票的收益； dp[i][k][0] 标识第i天交易了k次手里没有股票的收益
  • 状态转移：（买入股票的时候k+1）
  • dp[i][k][1]怎么获得，第i-1天持有股票没有卖出 dp[i-1][k][1] || 第i-1天没有股票买入dp[i-1][k-1][0] - prices[i]
  • dp[i][k][0]怎么获得，第i-1天没有股票没有卖入 dp[i-1][k][0] || 第i-1天有股票卖出 dp[i-1][k][0] + prices[i]
  • 基本情况：
  • dp[-1][k][0] = dp[i][0][0] = 0 （没开始，或没有交易，手里没有股票）
  • dp[-1][k][1] = dp[i][0][1] = -Infinity （没开始，或没交易， 手里有股票）
  • 优化后解法如下：
  • dp[i][0]和dp[i][1]分别表示第i笔交易买入和卖出时各自的最大收益
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        // k大于数组长度的一半等同于无限次买入卖出
        if (k >= prices.length / 2)
            return process(prices);
        // 0表示不持有股票, 1表示持有股票
        int[][] dp = new int[k + 1][2]; // 当前天依赖于前一天,因此不用添加前一天维度
        int res = 0;
        for (int i = 0; i <= k; i++) {
            dp[i][1] = Integer.MIN_VALUE;
        }
        for (int price : prices) {
            for (int j = 1; j <= k; j++) {
                dp[j][0] = Math.max(dp[j][0], dp[j][1] + price);
                dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - price);
            }
        }
        return dp[k][0];
    }
    public int process(int[] prices) {
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                res += prices[i] - prices[i - 1];
        }
        return res;
    }
}

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

sell[i]表示截至第i天，最后一个操作是卖出的最大收益；

buy[i]表示截至第i天，最后一个操作是买进的最大收益；

cool[i]表示截至第i天，最后一个操作是冷冻的最大收益；

递推公式：

sell[i] = buy[i-1] + prices[i] (第i天卖出)

buy[i] = max(cool[i-1] - prices[i], buy[i-1]) （第一项表示第i天买进，第二项表示第i天不操作）

cool[i] = max(sell[i-1], cool[i-1])（第一项表示第i天冰冻，第二项表示第i天不操作）

返回最后一天操作为卖出或者冰冻的最大值

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len <= 1) return 0;
        int[] sell = new int[len], buy = new int[len], cool = new int[len];
        buy[0] = -prices[0];
        for (int i = 1; i < len; i++) {
            sell[i] = buy[i - 1] + prices[i];
            buy[i] = Math.max(cool[i - 1] - prices[i], buy[i - 1]);
            cool[i] = Math.max(sell[i - 1], cool[i - 1]);
        }
        return Math.max(sell[len -1], cool[len - 1]);
    }
}

买卖股票的最佳时机含手续费

dp[i][1]表示第i天手上有股票，dp[i][0]表示第i天手上没有股票
递归方程：

dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]) （第二项表示在第i天买入股票）

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1] - fee) （第二项表示在第i天将股票卖出，需扣除手续费）

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        // dp[i][0]表示第i天不持有股票, dp[i][1]表示第i天持有股票
        int[][] dp = new int[len + 1][2];
        dp[0][1] = -prices[0];
        for (int i = 1; i <= len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);
        }
        return dp[len][0];
    }
}
Last modification：April 4, 2020
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏