121/122/123 Best Time to Buy and Sell Stock
121
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.
1. Not So Good Solution: Brute-Force
The naive try(Brute Force) to just scan through all the prices, and find the pair with the maximum difference, the time complexity is O(N^2).
2. Better Idea: Dynamic Programming
The main thought or the moral of the story is, "the harder you fall, the stronger you rise." To find the maximum profit, we should find the largest peak following lowest valley. Maintain two variables:
- MinPrice
- MaxProfit
Code:
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for(int i=0; i<prices.length; i++)
{
minPrice = Math.min(prices[i], minPrice);
maxProfit = Math.max(prices[i]-minPrice, maxProfit);
// if(prices[i]<minPrice)
// {
// minPrice = prices[i];
// }
// else if(prices[i]-minPrice > maxProfit)
// {
// maxProfit = prices[i]-minPrice;
// }
}
return maxProfit;
122. Best Time to Buy and Sell Stock II
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 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).
Resource: https://leetcode.com/articles/best-time-buy-and-sell-stock-ii/
Solution1: Greedy Algorithm - Simply One Pass
simply go on crawling over the slope and keep on adding the profit obtained from every consecutive transaction. Found the optimal solution at each steps.
If the second number if bigger than the first one, then the total sum we obtain will be the maximum profit.
public int maxProfit(int[] prices) {
int maxProfit = 0;
for(int i=0; i<prices.length-1; i++)
{
if(prices[i]<prices[i+1])
{
maxProfit += prices[i+1] - prices[i];
}
}
return maxProfit;
}
Complexity Analysis:
- Time complexity : O(n) Single pass.
Space complexity: O(1) Constant space needed.
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).
Solution1: Divide and Conquer(Dynamic Programming)
public int maxProfit(int[] prices) {
if(prices == null || prices.length<2)
{
return 0;
}
//store the traversal from index 0 to length-1 once, and then from index length-1 to 0
int[] preMax = new int[prices.length];
int[] postMax = new int[prices.length];
//Built the preMax Array from prices[1] to prices[length]
preMax[0] = 0;
int curMin = prices[0];
for(int i=1; i<prices.length; i++)
{
curMin = Math.min(curMin, prices[i]);
preMax[i] = Math.max(preMax[i-1], prices[i]-curMin);
}
//Built postMax array
postMax[prices.length-1] = 0;
int curMax = prices[prices.length-1];
for(int i=prices.length-2; i>0; i--)
{
curMax = Math.max(curMax, prices[i]);
//compare the more right one with the coming new profit
postMax[i] = Math.max(postMax[i+1], curMax-prices[i]);
}
int profit = 0;
for(int i=0; i<prices.length; i++)
{
profit = Math.max(profit, preMax[i]+postMax[i]);
}
return profit;
}
188. Best Time to Buy and Sell Stock IV
ay 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 k transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).