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

方法一：动态规划

题目中说明了在任意一个时间最多支持有一支股票，所以对应到每一天结束有两种状态：持有股票、不持有股票。

假设数组 dp[i][0] 表示第 i 天结束不持有股票的最大收入， dp[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]) $$

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; 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[n - 1][0];
    }
}

方法二：贪心

• 股票买卖策略
  • **单独交易日：**设今天价格 p1 、明天价格 p2 ，则今天买入、明天卖出可以赚取 p2 - p1
  • **连续上涨交易日：**设此上涨交易日股票价格分别为 p₁、p₂ ... p_n，则第一天买最后一天卖收益最大，即p_n - p₁；等价于每天都交易，即 p_n - p₁ = (p₂ - p₁) + (p₃ - p₂) + ... + (p_n - p_n-1)
  • **连续下跌交易日：**不买卖收益最大，即不亏钱

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

方法三：单调队列

从左向右扫描，遇到大于等于队尾价格的日子就推入，队列中表示持有股票的日子。一旦遇到当天价格小于队尾价格，那么表示队尾价格就是最高点了可以抛售，把队列中元素清空（表示股票抛售），加购这天价格低的股票等待售出。

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < prices.length; i++) {
            if (stack.isEmpty()) {
                stack.addLast(i);
            } else if (prices[i] >= prices[stack.peekLast()]) {
                stack.addLast(i);
            } else {
                res += (prices[stack.peekLast()] - prices[stack.peekFirst()]);
                stack = new LinkedList<>();
                stack.addLast(i);
            }
        }
        // 应对[1,2,3,4,5]这种一直上涨情况
        if (!stack.isEmpty()) {
            res += (prices[stack.peekLast()] - prices[stack.peekFirst()]);
        }
        return res; 
    }
}