-
Best Time to Buy and Sell Stock
reqest:只允许购买一次股票，即只能买入卖出一次
构建类似马尔科夫链的转态转移函数：
每个交易日可以又两种选择 buy 和sell
而buy和sell之间存在着先后关系，buy为第一次买入得到的最大利润，一定是负值，sell为第一次卖出得到的最大利润。
buy(i)=Math.max(buy(i-1),-prices[i]);
//实质是保存目前为止的最小交易值
sell(i)=Math.max(sell(i-1),buy(i-1)+prices[i]);
//在不断更新最小交易值的同时，不断判断目前交易天卖出是否是最大值。
必须先更新sell值，再更新buy,目的是为了利用上次迭代的buy去更新sell值
class Solution {
public int maxProfit(int[] prices) {
int buy=Integer.MIN_VALUE;
int sell=0;
int n=prices.length;
for(int i=0;i<n;i++){
sell=Math.max(sell,buy+prices[i]);
buy=Math.max(buy,-prices[i]);
}
return sell;
}
}
-
Best Time to Buy and Sell Stock III
request:可以最多两次次买入卖出
利用上面的思路，找状态转移方程，可以写出
sell2=Math.max(sell2,buy2+prices[i]);
//第二次买出的最大利润
buy2=Math.max(buy2,sell1-prices[i]);
//第二次买入的最大利润
sell1=Math.max(sell1,buy1+prices[i]);
//利用目前最大的买入利润得到第一次卖出的最大利润
buy1=Math.max(buy1,-prices[i]);
//保存第一次买入的最大利润，也就是交易额最小
所有变量是按照转态转移方程去不断更新优化，获得最佳值，
-
Best Time to Buy and Sell Stock II
requeat:可以多次买入买出，但每次买入必须在上一次卖出如果利用上述思路，继续使用状态转移方程，那么因为交易次数的不确定，最后得到的无数的状态转移方程，不可能实现，那么就要把状态转移方程合并成符合题目要求的样子
可以看到在Best Time to Buy and Sell Stock,单次交易的解决方法，那么无数次交易可以看成是无数次单次交易，先找到在某个时刻点买入的股票能连续获利的的最大值，一旦哪天卖出是相较上一天是亏本，则得到了一次买卖的收入，然后再次重复
其中的关键就是连续获利，也就是判断当天交易额是否比上一天高，高说明可以持续获利，低则说明买入的股票在上一天得到顶峰，上一天可以卖出，然后在寻找下一个连续获利的序列
与一次买卖最大的区别在于，每次卖出获利不是全局最优值，但是无数个局部最优值的叠加，贪婪算法。
class Solution {
public int maxProfit(int[] prices) {
int min=Integer.MAX_VALUE;
int max=0;
int n = prices.length;
for(int i=1;i<n;i++){
if(prices[i]>prices[i-1])
max+=prices[i]-prices[i-1]；
}
return max;
}
}
第二种方法，就是利用状态转移方程，对每次交易日的两种选择判断执行，这里的buy包含两种意思，之前卖了，当前天买入，或是之前买入了，然后一直保持在手里
class Solution {
public int maxProfit(int[] prices) {
int min=Integer.MAX_VALUE;
int max=0;
int n = prices.length;
int[] buy=new int[n+1];
buy[0]=Integer.MIN_VALUE;
int[] sell=new int[n+1];
for(int i=1;i<=n;i++){
sell[i]=Math.max(sell[i-1],buy[i-1]+prices[i-1]);
buy[i]=Math.max(buy[i-1],sell[i-1]-prices[i-1]);
}
return sell[n];
}
}
- Best Time to Buy and Sell Stock IV
request：
指定交易次数k,然后求最大利润。
同样的从一次买卖中寻找线索
二次买卖是在每个交易日更新二次交易值，那么K次买卖是不是能更新k次交易日，这个思路明显是正确的。
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if(k==0||n<2)
return 0;
if (n/2 < k){
return quickSolve(prices);
//因为当k次交易大于交易日的一般，也就是每天交易都打不到k次交易，则就可以按照无数次交易贪婪得到无数局部最优解的叠加
}
int[] hold = new int[k+1];
for(int i=0;i<=k;i++){
hold[i]=Integer.MIN_VALUE;
}
int[] unhold = new int[k+1];
hold[1]=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
for(int j=1;j<=k;j++){
unhold[j]=Math.max(unhold[j],hold[j]+prices[i]);
hold[j]=Math.max(hold[j],unhold[j-1]-prices[i]);
//在每个交易日对k个买卖的值执行更新
}
}
return unhold[k];
}
int quickSolve(int[] prices) {
int len = prices.length, profit = 0;
for (int i = 1; i < len; i++)
// as long as there is a price gap, we gain a profit.
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
return profit;
}
}
- Best Time to Buy and Sell Stock with Cooldown
request：可以多次交易，但是在卖出之后又一天的冷冻期不能买入
同样利用状态转移方程，
public int maxProfit(int[] prices) {
/*
重点在于表述状态转移方程，也就是从递归的角度描述，然后反向执行
首先股票包含的状态为sell buy cool
从递归的角度来看：
股票在第i天能够执行的操作有 buy sell ,并且在卖和买之间有一天的cool,但是在买和卖之间同样存在隐藏的cool_hidden;
判断第i天四种操作获取的最大利润
buy[i]:cool[i-1]-price[i];
cool_hidden[i]:cool_hidden[i-1];buy[i-1];
sell[i]:cool_hidden[i-1]+price[i];buy[i-1]+price[i];
cool[i]:sell[i-1];cool[i-1];
这个状态太长，开始降维合并：
首先，cool_hidden 可以合并到buy:hold操作就包含了buy和cool_hidden;
cool也可以列合并到sell：unhold操作包含sell和cool
hold[i]=max(hold[i-1],unhold[i-2]-price[i]);
unhold[i]=max(unhold[i-1],hold[i-1]+price[i]);
*/
int n = prices.length;
if(n<2)
return 0;
int[] hold=new int[n];
int[] unhold=new int[n];
hold[0]=-prices[0];
unhold[0]=0;
hold[1]=Math.max(hold[0],unhold[0]-prices[1]);
unhold[1]=Math.max(unhold[0],hold[0]+prices[1]);
for(int i=2;i<n;i++){
hold[i]=Math.max(hold[i-1],unhold[i-2]-prices[i]);
unhold[i]=Math.max(unhold[i-1],hold[i-1]+prices[i]);
}
return Math.max(hold[n-1],unhold[n-1]);
}
}
6. Best Time to Buy and Sell Stock with Transaction Fee
request:每笔交易需要手续费，但不限交易次数
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[] hold = new int[n];
int[] unhold=new int[n];
unhold[0]=0;
hold[0]=-prices[0];
for(int i=1;i<n;i++){
unhold[i]=Math.max(unhold[i-1],hold[i-1]+prices[i]-fee);
hold[i]=Math.max(hold[i-1],unhold[i-1]-prices[i]);
}
return unhold[n-1];
}
}
