121. Best Time to Buy and Sell Stock
122. Best Time to Buy and Sell Stock II
123. Best Time to Buy and Sell Stock III
188. Best Time to Buy and Sell Stock IV
309. Best Time to Buy and Sell Stock with Cooldown
714. Best Time to Buy and Sell Stock with Transaction Fee
这类问题的总结
- 在某一天如果不卖股票，利益就是前一天的利益
- 如果卖股票，要知道之前最低的成本是多少
121. Best Time to Buy and Sell Stock
class Solution {
//之前我们用O(n^2)的方法求一个价格后的最大价格
//转换思路
//维持某价格前的最小价格
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
//current price - previous minimum price, compare to the maxProfit
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
//update minPrice
minPrice = Math.min(minPrice, prices[i]);
}
return maxProfit;
}
}
122. Best Time to Buy and Sell Stock II
- 可以有多次交易
- 只要交易能赚钱（今天的价格比昨天的价格高），就交易
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int res = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1]) {
res += prices[i] - prices[i-1];
}
}
return res;
}
}
123. Best Time to Buy and Sell Stock III
//Time: O(kn^2) Space:O(kn)
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int[][] dp = new int[3][prices.length];
//dp[k][i] is the max profit with k transanctions up to i-th day
for (int k = 1; k <= 2; k++) {
for (int i = 1; i < prices.length; i++) {
int minCost = prices[0];
//if I want to sell stock in day i, I want to minimize the cost before i
//j is the buy day, i is sell day,
//dp[k-1][j-1] is the profit up to last transancation up to day j-1
//prices[j] - dp[k-1][j-1] is the minimum cost when I buy stock in day j
for (int j = 1; j <= i; j++) {
minCost = Math.min(minCost, prices[j] - dp[k-1][j-1]);
}
//dp[k][i-1]是不在第i天做交易，prices[i] - minCost是在第i天做交易
dp[k][i] = Math.max(dp[k][i-1], prices[i] - minCost);
}
}
return dp[2][prices.length-1];
}
}
//Time: O(kn) Space: O(kn)
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int[][] dp = new int[3][prices.length];
//dp[k][i] is the max profit with k transanctions up to i-th day
for (int k = 1; k <= 2; k++) {
int minCost = prices[0];
for (int i = 1; i < prices.length; i++) {
//if I want to sell stock in day i, I want to minimize the cost before i
minCost = Math.min(minCost, prices[i] - dp[k-1][i-1]);
//dp[k][i-1]是不在第i天做交易，prices[i] - minCost是在第i天做交易
dp[k][i] = Math.max(dp[k][i-1], prices[i] - minCost);
}
}
return dp[2][prices.length-1];
}
}
Time: O(n) Space: O(1)
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int cost1 = Integer.MAX_VALUE, profit1 = 0, cost2 = Integer.MAX_VALUE, profit2 = 0;
for (int i = 0; i < prices.length; i++) {
cost1 = Math.min(cost1, prices[i]);
profit1 = Math.max(profit1, prices[i] - cost1);
cost2 = Math.min(cost2, prices[i] - profit1);
profit2 = Math.max(profit2, prices[i] - cost2);
}
return profit2;
}
}
188. Best Time to Buy and Sell Stock IV
- 一个trick是如果我们可以进行的交易数量大于等于总天数的一半，相当于在这段时间内我们可以进行无限次的交易
- 这道题的trick用到了买卖股票2的思想，普通情况用到了买卖股票3的思想
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length == 0) return 0;
if (k >= prices.length / 2) return unlimitedTransanction(prices);
int[][] dp = new int[k+1][prices.length];
for (int i = 1; i <= k; i++) {
int minCost = prices[0];
for (int j = 1; j < prices.length; j++) {
minCost = Math.min(minCost, prices[j] - dp[i-1][j-1]);
//no transaction, profit is the same as previous day
//has transanction, profit is today's price - previous min cost
dp[i][j] = Math.max(dp[i][j-1], prices[j] - minCost);
}
}
return dp[k][prices.length-1];
}
private int unlimitedTransanction(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1]) profit += prices[i] - prices[i-1];
}
return profit;
}
}
714. Best Time to Buy and Sell Stock with Transaction Fee
class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices == null || prices.length == 0) return 0;
int n = prices.length;
int[] hold = new int[n], unhold = new int[n];
//在买股票时加交易费
hold[0] = -prices[0] - fee;
for (int i = 1; i < n; i++) {
//保持hold状态，或者在第i天买股票
hold[i] = Math.max(hold[i-1] , unhold[i-1] - prices[i] - fee);
//保持unhold状态，或者在第i天卖股票
unhold[i] = Math.max(unhold[i-1], hold[i-1] + prices[i]);
}
return Math.max(hold[n-1], unhold[n-1]);
}
}
309. Best Time to Buy and Sell Stock with Cooldown
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 1) return 0;
int n = prices.length;
int[] hold = new int[n];
int[] unhold = new int[n];
hold[0] = -prices[0];
hold[1] = Math.max(-prices[0], -prices[1]);
unhold[1] = Math.max(0, prices[1] - prices[0]);
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 unhold[n-1];
}
}
