121. Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
Solution: swipe from left to right, keeping a variable to store minimum value until the current index, and updating the current value - min to the maximum profit value.
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int minL = prices[0];
int max = 0;
for (int i = 1; i < prices.length; i++) {
max = Math.max(prices[i] - minL, max);
minL = Math.min(prices[i], minL);
}
return max;
}
122. Best Time to Buy and Sell Stock II
Say you have an array for which theithelement is the price of a given stock on dayi.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Solution: Since there is no limitation of number of transaction, we can make a transaction if we find a price increase.
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int maxProfit = 0;
for (int i = 0; i < prices.length - 1; i++) {
if (prices[i + 1] - prices[i] > 0) {
maxProfit += prices[i + 1] - prices[i];
}
}
return maxProfit;
}
123. Best Time to Buy and Sell Stock III
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Solution 1: An O(n^2) way is to partition the string into two parts, the cutting point can be at 1, 2, 3 ... n - 1. Find the max profit in each part and add them together. The max sum is the final result.
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int res = getProfit(prices, 0, prices.length - 1);
for (int i = 1; i < prices.length - 1; i++) {
if (prices[i] > prices[i - 1]) {
res = Math.max(res, getProfit(prices, 0, i) + getProfit(prices, i + 1, prices.length - 1));
}
}
return res;
}
private int getProfit(int[] prices, int start, int end) {
int min = prices[start];
int res = 0;
for (int i = start + 1; i <= end; i++) {
res = Math.max(prices[i] - min, res);
min = Math.min(min, prices[i]);
}
return res;
}
Solution 2: O(n). Let's have four variables, buy1, sell1, buy2, sell2. the relation is those four variables should be excuted in the order written. So the updating pattern is
sell2 = Math.max\(sell2, prices\[i\] + buy2\);
buy2 = Math.max\(buy2, sell1 - prices\[i\]\);
sell1 = Math.max\(sell1, prices\[i\] + buy1\);
buy1 = Math.max\(buy1, -prices\[i\]\);
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int buy1 = Integer.MIN_VALUE;
int buy2 = Integer.MIN_VALUE;
int sell1 = 0;
int sell2 = 0;
for (int i = 0; i < prices.length; i++) {
sell2 = Math.max(sell2, prices[i] + buy2);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell1 = Math.max(sell1, prices[i] + buy1);
buy1 = Math.max(buy1, -prices[i]);
}
return sell2;
}
188. Best Time to Buy and Sell Stock IV
Say you have an array for which theithelement is the price of a given stock on dayi.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Solution: A generalized pattern can be found to extend the number of transactions from 2 in the above problem to k. An optimization is if the number of transactions allowed is greater than prices.length/2, that is equivalent to unlimited number of transactions. We can call solution to 122. Best Time to Buy and Sell Stock II. to reduce the time complexity from O(nk) to O(n).
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length < 2 || k <= 0) {
return 0;
}
if (k > prices.length/2) {
return quickSolver(prices);
}
int[] buy = new int[k + 1];
int[] sell = new int[k + 1];
for (int i = 0; i <= k; i++) {
buy[i] = Integer.MIN_VALUE;
}
for (int i = 0; i < prices.length; i++) {
for (int j = k; j > 0; j--) {
sell[j] = Math.max(sell[j], prices[i] + buy[j]);
buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);
}
}
return sell[k];
}
private int quickSolver(int[] prices) {
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;
}
309. Best Time to Buy and Sell Stock with Cooldown
Say you have an array for which theithelement is the price of a given stock on dayi.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
- You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
- After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
Solution: the difference here buy[i] depends on sell[i - 2]
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int[] buy = new int[prices.length];
int[] sell = new int[prices.length];
buy[0] = -prices[0];
sell[0] = 0;
buy[1] = Math.max(-prices[0], -prices[1]);
sell[1] = Math.max(0, prices[1] - prices[0]);
for (int i = 2; i < prices.length; i++) {
sell[i] = Math.max(sell[i -1], buy[i - 1] + prices[i]);
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
}
return sell[prices.length - 1];
}
using rolling array to reduce the space complexity from O(n) to O(1)
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int sell0 = 0;
int buy = Math.max(-prices[0], -prices[1]);
int sell1 = Math.max(0, prices[1] - prices[0]);
for (int i = 2; i < prices.length; i++) {
int sellM1 = sell0;
sell0 = sell1;
sell1 = Math.max(sell1, buy + prices[i]);
buy = Math.max(buy, sellM1 - prices[i]);
}
return sell1;
}