1、前言

2、思路

此题使用动态规划的思路。首先题目有三种状态，分别为天数 i，交易限制 k，以及拥有或者不拥有股票状态0或1。
针对第 i 天在 k 次限制的情况下，拥有股票和不拥有股票的状态可能为：

• dp[i][k][0] = max {dp[i - 1][k][0], dp[i - 1][k][1] + price[i]}，解释为：第 i 天没有股票的情况下，有可能是第 i - 1 天就没股票了；或者第 i - 1 天有股票，但是第 i 天又卖出了股票
• dp[i][k][1] = max {dp[i - 1][k][1], dp[i - 1][k - 1][0] - price[i]}，解释为：第 i 天有股票的情况下，有可能是第 i - 1 天就有股票了；或者第 i - 1 天没股票，但是第 i 天又买入了股票，此时是买入股票，是一次新的操作，所以上一天的

基于这三种状态构造一个 dp 数组，最后我们要求的状态是 dp[n - 1][k][0]，因为最后卖出去才是利润最大的，所以最后一条拥有股票的状态为0。

此题中，k = 1，而转移方程中，k 都为1，所以 k 的状态不影响转移方程，可省略，将二维数组转化为一维数组。

3、代码

public class SellStockI {

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];

        for(int i = 0; i < n; i++){
            if(i - 1 == -1){
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], - prices[i]);
        }

        return dp[n - 1][0];
    }

    public static void main(String[] args) {
        int[] prices = new int[]{7,1,5,3,6,4};
        System.out.println(new SellStockI().maxProfit(prices));
    }
}