|
题目：
给定一段时间内每天的股票价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股
票，求最大的收益。
思路：
我们用 f[i]?表示第 i天结束之后的「累计最大收益」。根据题目描述，由于我们最多只能同时买入（持有）一支股票，并且卖出股票后有冷冻期的限制，因此我们会有三种不同的状态：
我们目前持有一支股票，对应的「累计最大收益」记为 f[i][0]；
我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f[i][1]；
我们目前不持有任何股票，并且不处于冷冻期中，对应的「累计最大收益」记为 f[i][2]。
这里的「处于冷冻期」指的是在第?i?天结束之后的状态。也就是说：如果第?i?天结束之后处于冷冻期，那么第?i+1?天无法买入股票。
class Solution {
public int maxProfit(int[] prices) {
if(prices.length==0){
return 0;
}
int n=prices.length;
// f[i][0]: 手上持有股票的最大收益
// f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
// f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
int[][] f = new int[n][3];
f[0][0]=-prices[0];//第一天收入是负的
for(int i=1;i<n;++i){
f[i][0]=Math.max(f[i-1][0],f[i-1][2]-prices[i]);
f[i][1]=f[i-1][0]+prices[i];
f[i][2]=Math.max(f[i-1][1],f[i-1][2]);
}
return Math.max(f[n-1][1],f[n-1][2]);
}
}
// class Solution {//算法优化
// public int maxProfit(int[] prices) {
// if (prices.length == 0) {
// return 0;
// }
// int n = prices.length;
// int f0 = -prices[0];
// int f1 = 0;
// int f2 = 0;
// for (int i = 1; i < n; ++i) {
// int newf0 = Math.max(f0, f2 - prices[i]);
// int newf1 = f0 + prices[i];
// int newf2 = Math.max(f1, f2);
// f0 = newf0;
// f1 = newf1;
// f2 = newf2;
// }
// return Math.max(f1, f2);
// }
// }
参考来自力扣309官方解答
|