力扣上几道关于股票最佳买卖时机的算法题，在此记录一下解题思路，对比官方的解题发现自己的思路还是太弱了
| 题号 | 题解 |
|---|---|
| 121. 买卖股票的最佳时机 | 暴力解法、动态规划 |
| 122. 买卖股票的最佳时机 II | 暴力搜索、贪心算法、动态规划 |
| 123. 买卖股票的最佳时机 III | 动态规划 |
| 188. 买卖股票的最佳时机 IV | 动态规划 |
| 309. 最佳买卖股票时机含冷冻期 | 动态规划 |
| 714. 买卖股票的最佳时机含手续费 | 动态规划 |
买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
解法一：对于这道题我首先想到的是暴力枚举出所有的利润然后找出利润最大的值，但是提交上去就超时了，暴力做法思路清晰简单，代码如下
public int maxProfit(int prices[]) {
int maxprofit = 0;
for (int i = 0; i < prices.length - 1; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxprofit) {
maxprofit = profit;
}
}
}
return maxprofit;
}解法二：这个解法是官方解法，我开始对解法一没找到优化的点，看了官方的思路后如醍醐灌顶，然后按照他的思路写了一遍，后面对比下和官方代码几乎一样。只需一次遍历，假设给定的数组为：[7, 1, 5, 3, 6, 4]。如果我们在图表上绘制给定数组中的数字，我们将会得到：
我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。
public static int maxProfit(int[] prices) {
int max = 0;
int min = prices[0];
for(int i=0;i<prices.length;i++){
if(prices[i]<min){
min = prices[i];
}else {
if(prices[i]-min>max){
max=prices[i]-min;
}
}
}
return max;
}买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解法一：同样需找一个历史低点，而后每天计算一下利润如果相比前一天赚钱了，就继续持有股票，如果亏钱了就应该在前一天卖出股票（因为只有在第二天才知道是不是应该继续持有股票），边界情况是最后一天如果是赚的就只能强制卖出股票了，因为没有下一天了。代码如下
public static int maxProfit2(int[] prices) {
//历史盈利
int profit=0;
//历史低点
int min=prices[0];
// 利润总和
int sumProfit = 0;
for(int i=1;i<prices.length;i++){
int temp = prices[i]-min;
if(temp>profit){
profit=prices[i]-min;
}else {
sumProfit = sumProfit+profit;
min = prices[i];
profit = 0;
}
// 清算利润
if(i==prices.length-1){
sumProfit = sumProfit+profit;
if(sumProfit<0){
sumProfit = 0;
}
}
}
return sumProfit;
}解法二：对于上面的解法是我的解题思路，更简单的是使用贪心算法，我们知道一天手里只有持有一笔交易，也就是说，当天可以卖了之后，又买一股。接下来，我们要做的，无非就是假设，如果今天我买了，明天是否赚？简而言之，如果明天卖出可以赚，那我今天就买入，你就说贪不贪心吧~。在这个思路的指导下，代码非常简洁
public int maxProfit(int[] prices) {
int ans = 0;
int n = prices.length;
for (int i = 1; i < n; ++i) {
ans += Math.max(0, prices[i] - prices[i - 1]);
}
return ans;
}买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 3-0= 3。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 4-1= 3
示例 2：输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
对于这个题我想了很久，没有一点思路，又去偷瞄看了官方的题解是用的动态规划，于是去找状态转移方程，结果还是没写出来，最终放弃了。。。即使是官方的状态转移方程我也是花了很久才理解它为什么是这样的。实际上我觉得官方的解释不好理解，我们先看一下官方的对于状态方程的解释，然后我再用我的理解对比一下官方动态规划解题思路如下
由于我们最多可以完成两笔交易，因此在任意一天结束之后，我们会处于以下五个状态中的一种：
未进行过任何操作；
只进行过一次买操作；
进行了一次买操作和一次卖操作，即完成了一笔交易；
在完成了一笔交易的前提下，进行了第二次买操作；
完成了全部两笔交易。
由于第一个状态的利润显然为 0，因此我们可以不用将其记录。对于剩下的四个状态，我们分别将它们的最大利润记为 buy1，sell1，buy2，sell2。对于 buy1而言，在第 i 天我们可以不进行任何操作，保持不变，也可以在未进行任何操作的前提下以 prices[i]的价格买入股票，那么 buy1的状态转移方程即为
对于 sell1 而言，在第 i 天我们可以不进行任何操作，保持不变，也可以在只进行过一次买操作的前提下以prices[i] 的价格卖出股票，那么 sell1 的状态转移方程即为
其中buy' 和 sell' 表示第 i-1 天的状态，以便于和第 i 天的状态 buy1 和 sell1 进行区分，在考虑边界条件时，我们需要理解下面的这个事实，无论题目中是否允许「在同一天买入并且卖出」这一操作，最终的答案都不会受到影响，这是因为这一操作带来的收益为零。因此，在状态转移时，我们可以直接写成：
根据状态转移方程我们可以得到代码
public int maxProfit(int[] prices) {
int n = prices.length;
int buy1 = -prices[0], sell1 = 0;
int buy2 = -prices[0], sell2 = 0;
for (int i = 1; i < n; ++i) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}我的理解：由于题目中要求最多两次买卖，那么我们最多就4个操作 [ 买 ，卖，买，卖 ]。所以buy1，sell1，buy2，sell2表示的是你每次操作时你的利润
- buy1：第一次买入股票，你的利润是
-prices[i]（因为你要花钱买股票，所以是个负数） - sell1：第一次卖出股票，你的利润是
prices[i] + buy1（当天的股价就是你赚到的钱+之前买入股票的成本 buy1，注意buy1是个负数） - buy2：第二次买入股票，你的利润是
-prices[i] + sell1（花钱买入股票+第一次卖出时的总利润） - sell2：第二次卖出股票，你的利润是
prices[i] + buy2（卖出股票所以当他股票就是赚到的钱+之前买入股票的剩余利润buy2）
我们要做的就是使每个阶段的利润最大，所以代码中全取最大值
