*121. 买卖股票的最佳时机

leetcode题目地址

贪心

记录最低价格作为买入价格，并用当前价格减去最低价格获得利润。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

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

*动态规划

首先需要理清楚dp数组的含义，dp数组中存储的是持有或不持有的利润，而不是当天买入或卖出的利润。

dp[i][0]表示第i天持有股票的利润，可以之前买入也可以当天买入，取二者最大值保留即可，即，dp[i][0] = max(dp[i-1][0], -prices[i])
dp[i][1]表示第i天不持有股票的利润，可以之前卖出也可以当天卖出，同样取二者最大值保留，即，dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])

// java
class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n][2];dp[0][0] = -prices[0];dp[0][1] = 0;for(int i=1; i<n; i++){// 持有dp[i][0] = Math.max(dp[i-1][0], -prices[i]);dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]+prices[i]);}return dp[n-1][1];}
}

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

leetcode题目地址

使用二维dp数组，dp[i][0]表示第i天持有股票的价值，dp[i][1]表示第i天不持有股票的价值。

• dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]);
  第i天持有股票的价值 = max(前一天就持有股票的价值，当天买入股票)
• dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]+prices[i]);
  第i天不持有股票的价值 = max(前一天就不持有股票的价值，当天卖出股票)

时间复杂度： $O(n)$
空间复杂度： $O(n)$

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

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

leetcode题目地址

使用二维dp数组来记录每天的状态下的最大收益，即：
dp[i][j]表示第i天的第j个状态的最大收益。

共有五个状态

• 0 未操作（可省略）
• 1 第一次持有
• 2 第一次不持有
• 3 第二次持有
• 4 第二次不持有

本题的难点在于初始化。

本题要求每次购入之前不许持有股票，也就是卖出后才能重新购入。

因此，初始化如下：

• dp[0][0]表示第0天不操作，收益为0.
• dp[0][1]表示第0天第一次持有（即当天第一次买入），收益为-prices[0]
• dp[0][2]表示第0天第一次不持有（即当天第一次卖出），收益为dp[0][1]+prices[0]，也就是0
• dp[0][3]表示第0天第二次持有（即当天第二次买入），收益为dp[0][2]-prices[0]，也就是-prices[0]
• dp[0][4]表示第0天第二次不持有（即当天第二次卖出），收益为dp[0][2]+prices[0]，也就是0

dp[0][3]和dp[0][4]比较难想到，因为它是在同一天进行的两次操作。

每一个状态的更新，依赖于前一个状态的结果。也就是持有的状态下才能卖出、不持有的状态下才能买入。

dp[i][0]可以忽略不使用，因为在整体状态转移中和这个状态没有关系。（或者可以理解为第一次买入是在未操作的状态上进行的）

最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。可以这么理解：如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[i][4]已经包含了dp[i][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][5];dp[0][1] = -prices[0];dp[0][3] = -prices[0];for(int i=1; i<prices.length; i++){dp[i][1] = Math.max(dp[i-1][1], -prices[i]);dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]+prices[i]);dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2]-prices[i]);dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3]+prices[i]);}return dp[prices.length-1][4];}
}