121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
123. 买卖股票的最佳时机 III
188. 买卖股票的最佳时机 IV
309. 最佳买卖股票时机含冷冻期
714. 买卖股票的最佳时机含手续费
121、限定只能买卖一次
方一：一次遍历法记录最大差值！
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}
方二：记录买卖最大差值！
public class Solution {
public int maxProfit(int prices[]) {
int buy = Integer.MIN_VALUE, sell = 0;
for (int p : prices)
{
buy = max(buy, -p); // max(不买，买了)
sell = max(sell, buy + p); // max(不卖，卖了)
}
return sell;
}
}
122、要求多次买卖
方一：动态规划
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
// 定义状态
// dp[i][0] 表示第i天交易完后手里没有股票的最大利润，
// dp[i][1] 表示第i天交易完后手里持有一支股票的最大利润（i从0开始）。
int[][] dp = new int[n][2];
//初始值
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < n; i++){
// 如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即dp[i−1][0]，或者前一天结束的时候手里持有一支股票，即dp[i-1][1]，这时候我们要将其卖出，并获得prices[i]的收益。因此为了收益最大化，我们列出如下的转移方程：------------------------------------------------------------------------------------------
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
// 再来考虑dp[i][1]，按照同样的方式考虑转移状态，那么可能的转移状态为前一天已经持有一支股票，即dp[i−1][1]，或者前一天结束时还没有股票，即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][0];
}
}
方二：
class Solution {
public int maxProfit(int[] prices) {
int buy = Integer.MIN_VALUE, sell = 0;
// 因为需要多次买卖，所以每天都要尝试是否能获得更多利润
for (int p : prices)
{
int buynow = max(buy, sell - p); //max(不买，卖了买)
int sellnow = max(sell, buy + p); //max(不卖，买了卖)
buy = buynow;
sell = sellnow;
}
return sell;
}
}
123、只能交易两次
class Solution {
public int maxProfit(int[] prices) {
// 思路与算法
// 由于我们最多可以完成两笔交易，因此在任意一天结束之后，我们会处于以下五个状态中的一种：
// 未进行过任何操作；
// 只进行过一次买操作；
// 进行了一次买操作和一次卖操作，即完成了一笔交易；
// 在完成了一笔交易的前提下，进行了第二次买操作；
// 完成了全部两笔交易。
//由于第一个状态的利润显然为0，因此我们可以不用将其记录。对于剩下的四个状态，我们分别将它们的最大最大利润记为buy1、sell1、buy2、sell2。
//初始化
int buy1 = -prices[0], sell1 = 0;
int buy2 = -prices[0], sell2 = 0;
for(int i = 1; i < prices.length; i++){
buy1 = Math.max(buy1, -prices[i]); // 第一次买 -p
sell1 = Math.max(sell1, buy1 + prices[i]); // 第一次卖 buy1 + p
buy2 = Math.max(buy2, sell1 - prices[i]); // 第一次卖了后现在买 sell1 - p
sell2 = Math.max(sell2, buy2 + prices[i]); // 第二次买了后现在卖 buy2 + p
}
return sell2;
}
}
由于我们可以进行不超过两笔交易，因此最终的答案在 0、sell1、sell2中，且为三者中的最大值。然而我们可以发现，由于在边界条件中 sell1和sell2的值已经为 0，并且在状态转移的过程中我们维护的是最大值，因此sell1和 sell2最终一定大于等于 0。同时，如果最优的情况对应的是恰好一笔交易，那么它也会因为我们在转移时允许在同一天买入并且卖出这一宽松的条件，从 sell1转移至sell2，因此最终的答案即为sell2。
188、限定只能买卖K次
class Solution {
public int maxProfit(int k, int[] prices) {
int[] buy = new int[k+1];
int[] sell = new int[k+1];
Arrays.fill(buy,Integer.MIN_VALUE);
Arrays.fill(sell,0);
for(int price : prices){
for(int i = 1; i <= k; i++){
buy[i] = Math.max(buy[i], sell[i-1] - price); //max(不买,卖了买)
sell[i] = Math.max(sell[i],buy[i] + price); //max(不卖,买了卖)
}
}
return sell[k];
}
}
309、限定条件：卖出股票后第二天无法买入股票
class Solution {
public int maxProfit(int[] prices) {
int buy = -prices[0], sell = 0, lock = 0;
//因为有冷冻期，所以定义遍历 lock 表示无法交易的时候
for(int p : prices){
int buynow = Math.max(buy, lock - p); //max(不买，冷冻期后买入)
int sellnow = Math.max(sell, buy + p); //max(不卖，买后卖)
lock = sell;
buy = buynow;
sell = sellnow;
}
return sell;
}
}
714、限定条件买入或卖出时要扣除手续费
class Solution {
public int maxProfit(int[] prices, int fee) {
int buy = Integer.MIN_VALUE, sell = 0;
//在买入或卖出时减去手续费即可
for（int p : prices){
int buynow = max(buy, sell - p - fee); //max(不买，卖了买 - 手续费)
int sellnow = max(sell, buy + p); //max(不卖, 买了卖)
buy = buynow;
sell = sellnow;
}
return selln;
}
}
