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是如果我們可以進行的交易數(shù)量大于等于總天數(shù)的一半冯凹，相當于在這段時間內我們可以進行無限次的交易
- 這道題的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狀態(tài)炒嘲，或者在第i天買股票
hold[i] = Math.max(hold[i-1] , unhold[i-1] - prices[i] - fee);
//保持unhold狀態(tài)宇姚，或者在第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];
}
}
