-
Best Time to Buy and Sell Stock
reqest:只允許購買一次股票萧芙，即只能買入賣出一次
構建類似馬爾科夫鏈的轉態(tài)轉移函數：
每個交易日可以又兩種選擇 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:可以最多兩次次買入賣出
利用上面的思路绩脆，找狀態(tài)轉移方程，可以寫出
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]);
//保存第一次買入的最大利潤橄抹，也就是交易額最小
所有變量是按照轉態(tài)轉移方程去不斷更新優(yōu)化靴迫，獲得最佳值，
-
Best Time to Buy and Sell Stock II
requeat:可以多次買入買出楼誓，但每次買入必須在上一次賣出如果利用上述思路玉锌，繼續(xù)使用狀態(tài)轉移方程，那么因為交易次數的不確定疟羹，最后得到的無數的狀態(tài)轉移方程主守，不可能實現，那么就要把狀態(tài)轉移方程合并成符合題目要求的樣子
可以看到在Best Time to Buy and Sell Stock,單次交易的解決方法榄融，那么無數次交易可以看成是無數次單次交易参淫，先找到在某個時刻點買入的股票能連續(xù)獲利的的最大值，一旦哪天賣出是相較上一天是虧本愧杯，則得到了一次買賣的收入涎才，然后再次重復
其中的關鍵就是連續(xù)獲利，也就是判斷當天交易額是否比上一天高力九，高說明可以持續(xù)獲利耍铜，低則說明買入的股票在上一天得到頂峰，上一天可以賣出跌前，然后在尋找下一個連續(xù)獲利的序列
與一次買賣最大的區(qū)別在于棕兼，每次賣出獲利不是全局最優(yōu)值，但是無數個局部最優(yōu)值的疊加舒萎，貪婪算法程储。
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;
}
}
第二種方法臂寝，就是利用狀態(tài)轉移方程章鲤，對每次交易日的兩種選擇判斷執(zhí)行，這里的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次交易，則就可以按照無數次交易貪婪得到無數局部最優(yōu)解的疊加
}
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個買賣的值執(zhí)行更新
}
}
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：可以多次交易辜妓，但是在賣出之后又一天的冷凍期不能買入
同樣利用狀態(tài)轉移方程枯途，
public int maxProfit(int[] prices) {
/*
重點在于表述狀態(tài)轉移方程，也就是從遞歸的角度描述籍滴，然后反向執(zhí)行
首先股票包含的狀態(tài)為sell buy cool
從遞歸的角度來看：
股票在第i天能夠執(zhí)行的操作有 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];
這個狀態(tài)太長酪夷，開始降維合并：
首先，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:每筆交易需要手續(xù)費孽惰，但不限交易次數
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];
}
}
