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]);
}
}
[leetcode309] Best Time to Buy and Sell Stock with Cooldown
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
推荐阅读更多精彩内容
- Description Say you have an array for which the ith eleme...
- Description Your are given an array of integers prices, f...
- 感觉不像股票系列,倒是很像house rubery那个题。dp function的含义是"sold[i]:第i天卖...
- 原题地址 https://leetcode.com/problems/best-time-to-buy-and-s...