一、买卖股票
121：你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润
贪心：
class Solution {public int maxProfit(int[] prices) {int length = prices.length;int min = prices[0];int cur = 0;int max = 0;for (int i = 1; i < length; i++) {//记录prices[i]之前的最小值min = Math.min(min, prices[i]);//第i天卖出能收到的最大收益cur = prices[i] - min;max = Math.max(max,cur);}return max;}
}二、买卖股票II
122：设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
贪心：只要出现递增就算进去
class Solution {public int maxProfit(int[] prices) {int result = 0;for(int i=1;i<prices.length;i++){if(prices[i]-prices[i-1]>0)result+=prices[i]-prices[i-1];}return result;}
}动态规划：
class Solution {public int maxProfit(int[] prices) {int length = prices.length;int[][] dp = new int[length][2];//dp[i][0]，第i天不持有股票的最大收益//dp[i][1]，第i天持有股票的最大收益dp[0][0]=0;dp[0][1]=-prices[0];for(int i =1;i<length;i++){//第i天不持有：两种情况：1.前一天持有，今天卖掉,则加上今天的票价 2.前一天维持有，还是昨天的收益，光有股票不卖的话，没有收益来源，收益不变dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);//第i天持有：两种情况：1.前一天持有，就是昨天的收益，因为没卖就没收益 2.如果前一天没持有，减去今天的票价,买进来需要花费dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);}return Math.max(dp[length-1][0],dp[length-1][1]);}
}三、买卖股票III
123：设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
class Solution {public int maxProfit(int[] prices) {int length = prices.length;int[][] dp = new int[length][5];dp[0][0]=0;dp[0][1]=-prices[0];dp[0][2]=0;dp[0][3]=-prices[0];dp[0][4]=0;for(int i =1;i< length;i++){//五种状态是第i天所处的状态，而不是第i天所做的操作//d[i][0]处于什么操作都没做的状态dp[i][0]=dp[i-1][0];//d[i][1]处于买入了一次股票状态dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);//d[i][2]处于卖出了一次股票状态dp[i][2]=Math.max(dp[i-1][1]+prices[i],dp[i-1][2]);//d[i][3]处于买入了两次股票状态dp[i][3]=Math.max(dp[i-1][2]-prices[i],dp[i-1][3]);//d[i][4]处于卖出了两次股票状态dp[i][4]=Math.max(dp[i-1][3]+prices[i],dp[i-1][4]);}return dp[length-1][4];}
}四、买卖股票IV
188：设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
class Solution {public int maxProfit(int k, int[] prices) {int length = prices.length;if(length==0)return 0;int[][] dp = new int[length][2*k+1];for(int i=0;i<2*k+1;i++){if(i%2==0)dp[0][i]=0;elsedp[0][i]=-prices[0];}for(int i=1;i<length;i++){dp[i][0]=dp[i-1][0];for(int j =1;j<2*k+1;j++){if(j%2==1)//买入dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);elsedp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]+prices[i]);}}return dp[length-1][2*k];}
}五、买卖股票含冷冻期
309：设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
class Solution {public int maxProfit(int[] prices) {int length = prices.length;int[][] dp = new int[length][4];//四种状态//买入股票的状态dp[0][0]=-prices[0];//卖出股票状态，已经度过冷冻期dp[0][1]=0;//今天卖出股票dp[0][2]=0;//今天为冷冻期dp[0][3]=0;for(int i=1;i<length;i++){//买入状态：前一天的买入状态，前一天的度过冷冻状态，前一天的冷冻状态dp[i][0]=Math.max(Math.max(dp[i-1][0],dp[i-1][1]-prices[i]),dp[i-1][3]-prices[i]);//卖出度过冷冻期状态：前一天的冷冻期状态，前一天的度过冷冻状态dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3]);//今天卖出股票状态：前一天为买入期状态，dp[i][2]=dp[i-1][0]+prices[i];//今天冷冻期状态：前一天卖出股票dp[i][3]=dp[i-1][2];}return Math.max(Math.max(dp[length-1][1],dp[length-1][2]),dp[length-1][3]);}
}