Leetcode121，股票只能买卖一次，问最大利润。
示例 :
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
思路分析：
法1：双指针：定义双指针，一个指向买入，一个指向卖出，遍历数组，更新最大值。
法2：贪心：因为只有一次买入卖出，保证以最低的价钱买入，然后遍历数组，更新最大值。
法3：动态规划：一天只有两个状态：持有和不持有，遍历数组返回最后一天的情况
dp[i][0]和dp[i][1]分别代表第i天持有和不持有股票所得的现金。- 状态转移方程：对于当前填持有和不持有，我们分别分析其上一天的情况
- 持有状态，上一天持有或不持有（
现在买入，即-prices[i]）最大值； - 不持有状态，上一天可以是持有（
现在卖了，即prices[i - 1][0] + prices[i]）或不持有最大值。
代码实现：代码1：双指针
public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) return 0; int start = 0, end = 1, max = 0; while (start < end && end < prices.length) { if (prices[start] >= prices[end]) { start = end++; } else { max = Math.max(max, prices[end] - prices[start]); end++; } } return max; }
代码2：贪心
public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) return 0; int low = Integer.MAX_VALUE; int max = 0; for (int i = 0; i < prices.length; ++i) { low = Math.min(low, prices[i]); max = Math.max(max, prices[i] - low); } return max; }
代码3：动态规划
public int maxProfit(int[] prices) { int len = prices.length; if (prices == null || len == 0) return 0; int[][] dp = new int[len][2]; dp[0][0] = -prices[0]; dp[0][1] = 0; for (int i = 1; i < len; ++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[len - 1][1]; }
Leetcode122，可以多次买卖股票，问最大收益。
示例：
输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
思路分析：
法1：贪心算法：实现上述需求每次交易只要买入小于卖出，即保证每次交易都有收益即可！
法2：动态规划：这里与上题唯一的区别是多次买卖股票。关键点：
- 当
dp[i][0]，即第i天持有股票时，是在之前利润（前一天卖出的最大利润，前一天必须卖出）基础上在买入，即dp[i - 1][1] - prices[i]。，上题只有一次买入。 - 对于第i天不持有股票，与上边相同。
代码实现：代码1：贪心
public int maxProfit(int[] prices) { int n = prices.length; if (prices == null || n == 0) return 0; int max = 0; for (int i = 1; i < n; i++) { if (prices[i] > prices[i - 1]) { max += prices[i] - prices[i - 1]; } } return max; }
代码2：动态规划
public int maxProfit(int[] prices) { int len = prices.length; if (prices == null || len == 0) return 0; int[][] dp = new int[len][2]; dp[0][0] = -prices[0]; dp[0][1] = 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][1]; }
Leetcode123，最多买卖两次，问最大收益。
示例 :
输入: [3,3,5,0,0,3,1,4] 输出: 6 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
思路分析：
与案例2不同的是，本例限制买入卖出的次数，最多买入两次。相对来说，难度大了很多。对于下面的情况：
1 5 2 8 3 10
第一天买第二天卖，第三天买第四天卖，第五天买第六天卖，三次收益分别是 4，6，7，最高的两次就是 6 + 7 = 13 了，但是我们第二天其实可以不卖出，第四天再卖出，那么收益是 8 - 1 = 7，再加上第五天买入第六天卖出的收益就是 7 + 7 = 14了。
所以当达到了一个高点时不一定要卖出！！！---用动态规划（动态规划关键就是数组定义和状态转移方程！！！）
法1：动态规划：当然我们可以暴力的想一下，当我们计算第 i 天的收益时进行了k次交易，我们可以选择：
- 不买入卖出，即第
i天的收益 等于第i - 1天的收益. - 卖出，追求更大收益，这里就要在
0到i-1天就要选择一天买入。多选择了一次买入，那在买入之前已经进行了k-1次买卖。
即：当用 dp[i][k] 表示前i天最多交易k次的最高收益（数组定义），求解可分为两部分（状态转移）
- 不操作：
dp[i][k] = dp[i-1][k] - 之前有买入：在第 j 天买入，收益就是
prices[i] - （prices[j] - dp[j][k-1]），我们利用动态规划找第j天（prices[j] - dp[j][k-1]）最小值，即代码中的min
法2：状态机，一共有五种状态：不操作，第一次买入/卖出和第二次买入/卖出。
dp[i][j]表示第i天，状态为j所剩最大现金。，注：dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态- 对于i天都有两个状态：持有和不持有，我们分别考虑前一天的状态。参照122题求解，只不过我们进行两次这样的操作。
代码实现：代码1：动态规划
public int maxProfit(int[] prices) { int n = prices.length; if (prices == null || n == 0) return 0; int K = 2; int[][] dp = new int[n][K + 1]; for (int k = 1; k <= K; k++) { int min = prices[0]; for (int i = 1; i < n; i++) { //找出第 1 天到第 i 天 prices[buy] - dp[buy][k - 1] 的最小值 min = Math.min(prices[i] - dp[i][k - 1], min); //比较不操作和选择一天买入的哪个值更大 dp[i][k] = Math.max(dp[i - 1][k], prices[i] - min); } } return dp[n - 1][K]; }
代码2：状态机
public int maxProfit(int[] prices) { int n = prices.length; if (prices == null || n == 0) return 0; int[][] dp = new int[n][5]; dp[0][1] = dp[0][3] = -prices[0]; for (int i = 1; i < n; ++i) { dp[i][0] = dp[i - 1][0]; dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - 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[n - 1][4]; }
Leetcode188，最多买卖K次，问最大收益。
示例 :
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
思路分析：动态规划：无论买卖多少次，每天我们都对应两个状态。我们这里使用123中状态机的解法：
dp[i][j] 表示第i天，状态为j，所剩下的最大现金是dp[i][j]。- j的状态表示为：0 表示不操作；1 第一次买入，2 第一次卖出；3 第二次买入，4 第二次卖出... 即除了0之外，奇数状态买入，偶数状态卖出。
- 注意j的步长为2（每天），共进行2*k次买入卖出，注意j循环时不要越界！测试用例中含有0，特判！
状态转移方程为：
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]); dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
- 注意初始条件：当卖出，即
dp[0][j] == 0, j为偶数；当买入，即dp[0][j] = -prices[0]，j为奇数。 - 按照定义最终有2k个状态，所以返回
dp[n - 1][2 * k]。
时间复杂度：O(KN)，K为交易的次数。
代码实现：
public int maxProfit(int k, int[] prices) { int n = prices.length; if (prices == null || n == 0) return 0; int[][] dp = new int[n][2 * k + 1]; for (int j = 1; j < 2 * k; j += 2) { dp[0][j] = -prices[0]; } for (int i = 1; i < n; i++) { for (int j = 0; j < 2 * k - 1; j += 2) { dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]); dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); } } return dp[n - 1][2 * k]; }
Leetcode309， 可以多次买卖但每次卖出有冷冻期1天。
示例 :
输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
思路分析：动态规划：本题在122基础上加入冷冻期，这里我们第i天分为三种状态，分别用0~2表示：
- 持有股票：可能是前一天就持有或者度过冷冻期又买入（不能直接买入）的最大值。
- 不持有股票，处于冷冻期：原因是当前卖出了股票，得到收益。
- 不持有股票，不在冷冻期：可能前一天在冷冻期或者不在冷冻期的最大值。
注意：最后我们需要返回不持有股票的最大值。
代码实现：
public int maxProfit(int[] prices) { int n = prices.length; if (prices == null || n == 0) return 0; int[][] dp = new int[n][3]; dp[0][0] = -prices[0]; for (int i = 1; i < n; ++i) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]); // 不持有股票 dp[i][1] = dp[i - 1][0] + prices[i]; dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]); } return Math.max(dp[n - 1][1], dp[n - 1][2]); }
Leetcode714， 可以多次买卖，但每次有手续费。
示例 :
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2 输出: 8 解释: 能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
思路分析：本题在122基础上加入手续费，我们只需要在每次卖出时减去手续费即可（即需要支付手续费）！
代码实现：
public int maxProfit(int[] prices, int fee) { int n = prices.length; if (prices == null || n == 0) return 0; 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], dp[i - 1][1] - prices[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee); } return dp[n - 1][1]; }
