Best Time to Buy and Sell Stock II
先说买卖股票II，这题没有交易次数的限制条件
我们定义两个dp数组, hold[n]和unhold[n]
-
hold[i]- the maximum profit I can have ends at ith day -
unhold[i]- maximum profit I can have ends at ith day
初始化
-
hold[0] = -prices[0]- 第一天买入profit是-prices[0] -
unhold[0] = 0- 第一天不买，profit是0
结果 - unhold[n - 1] - unhold[n - 1]一定大于hold[n - 1]
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int n = prices.length;
int[] hold = new int[n];
int[] unhold = new int[n];
hold[0] = -prices[0];
unhold[0] = 0;
for (int i = 1; i < n; i++) {
hold[i] = Math.max(hold[i - 1], unhold[i - 1] - prices[i]);
unhold[i] = Math.max(unhold[i - 1], hold[i - 1] + prices[i]);
}
return unhold[n - 1];
}
}
Best Time to Buy and Sell Stock
买卖股票I是在买卖股票二上加入了限制条件，即最多只能有一次交易
我们稍微的对hold[n]的转移方程做出修改即可 - hold[i] - Math.max(unhold[i - 1], -prices[i])
因为只能买一次，所以如果一定要在第ith day买入，那这种情况下unhold[i]就是-prices[i]
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int n = prices.length;
int[] hold = new int[n];
int[] unhold = new int[n];
hold[0] = -prices[0];
unhold[0] = 0;
for (int i = 1; i < n; i++) {
hold[i] = Math.max(hold[i - 1], -prices[i]);
unhold[i] = Math.max(unhold[i - 1], hold[i - 1] + prices[i]);
}
return unhold[n - 1];
}
}
Best Time to Buy and Sell Stock IV
买卖股票IV限制了最多k次的交易次数
我们的dp数字要加上第二个维度，即交易次数
- 定义
hold[n][k + 1]- hold[i][j] - the maximum profit I can have when I hold the stock at ith day with at most j times transaction - 定义
unhold[n][k + 1]- unhold[i][j] - the maximum profit I can have when I unhold the stock at ith day with at most j times transaction
初始化
unhold[0][1...k] = 0 - 对于第1天（index = 0），我不持有股票，我的maximum profit是0
unhold[0][1...k] = -prices[0] - 对于第1天（index = 0），我持有股票，我的maximum profit是-prices[0]
结果
unhold[n - 1][k]
最后我们额外的处理一种特出情况，就是当k的值大于prices.length / 2时，这题就被转换到了买卖股票II的问题
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
if (k > prices.length / 2) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
profit += Math.max(0, prices[i] - prices[i - 1]);
}
return profit;
}
int n = prices.length;
int[][] hold = new int[n][k + 1]; // hold[i][j] - the maximum profit i can make when i make at most j times of transactions at ith day with stock in hand
int[][] unhold = new int[n][k + 1]; // unhold[i][j] - hold[i][j] - the maximum profit i can make when i make at most j times of transactions at ith day without stock in hand
for (int j = 1; j <= k; j++) {
hold[0][j] = -prices[0];
unhold[0][j] = 0;
for (int i = 1; i < n; i++) {
hold[i][j] = Math.max(hold[i - 1][j], unhold[i - 1][j - 1] - prices[i]);
unhold[i][j] = Math.max(unhold[i - 1][j], hold[i - 1][j] + prices[i]);
}
}
return unhold[n - 1][k];
}
}
Best Time to Buy and Sell Stock III
买卖股票III问的是最多的交易次数是2的时候，最大profit是多少。把买卖股票IV里的k替换成2即可。
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int n = prices.length;
int[][] hold = new int[n][3];
int[][] unhold = new int[n][3];
for (int j = 1; j <= 2; j++) {
hold[0][j] = -prices[0];
unhold[0][j] = 0;
for (int i = 1; i < n; i++) {
hold[i][j] = Math.max(hold[i - 1][j], unhold[i - 1][j - 1] - prices[i]);
unhold[i][j] = Math.max(unhold[i - 1][j], hold[i - 1][j] + prices[i]);
}
}
return unhold[n - 1][2];
}
}
Best Time to Buy and Sell Stock with Transaction Fee
这题是买卖股票且每次交易要收手续费，但不限制交易次数。把买卖股票II的转移方程稍作修改
在买卖股票II中，hold[n]的
转移方程是 - hold[i] = Math.max(hold[i - 1], unhold[i - 1] - prices[i])
初始化是 - hold[0] = -prices[0]
而这题hold[n]的
转移方程是 - hold[i] = Math.max(hold[i - 1], unhold[i - 1] - prices[i] - fee);
初始化是 - hold[0] = -prices[0] - fee
class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices == null || prices.length <= 1) {
return 0;
}
int n = prices.length;
int[] hold = new int[n];
int[] unhold = new int[n];
hold[0] = -prices[0] - fee;
unhold[0] = 0;
for (int i = 1; i < n; i++) {
hold[i] = Math.max(hold[i - 1], unhold[i - 1] - prices[i] - fee);
unhold[i] = Math.max(unhold[i - 1], hold[i - 1] + prices[i]);
}
return unhold[n - 1];
}
}
Best Time to Buy and Sell Stock with Cooldown
这题要求如果你卖出了股票，那卖出股票的后一天，你不能进行买入操作，你只能休息一天。
这题我们定义三种状态
-
buy[i]- before or at ith day, the maximum profit I can have if the last action is buy -
sell[i]- before or at ith day, the maximum profit I can have if the last action is sell -
rest[i]- before or at ith day, the maximum profit I can have if the last action is rest
转移方程
buy[i] = max(buy[i - 1], rest[i - 1] - prices[i])
sell[i] = max(sell[i - 1], buy[i - 1] + prices[i])
rest[i] = max(rest[i - 1], buy[i - 1], sell[i - 1])
初始化
buy[0] = -prices[0]-
sell[0] = Integer.MIN_VALUE// 这种情况不可能发生，第1天（index 0）上，不能发生sell action，用Integer.MIN_VALUE来表示这种状态 rest[0] = 0
结果
max(rest[n - 1], sell[n - 1])
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int n = prices.length;
int[] buy = new int[n]; // buy[i] - before or at ith day, the maximum profit you can have when the last action is buy
int[] sell = new int[n]; // hold[i] - before or at ith day, the maximum profit you can have when the last action is sell
int[] rest = new int[n]; // rest[i] - before or at ith day, the maximum profit you can have when the last action is rest
buy[0] = -prices[0];
sell[0] = Integer.MIN_VALUE;
rest[0] = 0;
for (int i = 1; i < n; i++) {
buy[i] = Math.max(buy[i - 1], rest[i - 1] - prices[i]);
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
rest[i] = Math.max(rest[i - 1], Math.max(buy[i - 1], sell[i - 1]));
}
return Math.max(rest[n - 1], sell[n - 1]);
}
}
