Given an array of stock prices where prices[i] = stock price on day i, design an algorithm to find the maximum profit with one transaction.
You have to buy the stock before selling it.
Example
Input: [7, 1, 5, 3, 6, 4]
Output: 5 Buy at 1 and sell at 6
Analysis
The brute force solution is for each number find the potential max profit if make the purchase here. Nested loops so O(n^2). Alright so how do we get to linear time?
Approach
1. optimal subproblems
maxProfit(n) = maximum profit you can get at day n
2. solve by prefix
maxProfit(n) = Math.max(maxProfit(n-1), prices[n] - localMin)
3. topo order
for i from 2 to n
4. base cases
maxProfit(0) = 0
5. answer
return maxProfit(n)
Code
public int maxProfit(int[] prices) {
// edge cases
if (prices == null || prices.length == 0) {
return 0;
}
// create memo table
int[] memo = new int[prices.length];
// init base case
memo[0] = 0;
int localMin = prices[0];
// topo order
for (int i = 1; i < prices.length; i++) {
localMin = Math.min(localMin, prices[i]);
memo[i] = Math.max(memo[i-1], prices[i] - localMin);
}
// answer
return memo[memo.length - 1];
}
Time & Space Complexity
Time: one loop so O(n)
Space: store the partial answers to all subproblems so O(n)
Follow Up #1
Can you do Q1 in O(1) space?
Analysis
maxProfit(n) = Math.max(maxProfit(n-1), prices[n] - localMin) only needs the previous subproblem and localMin which we already have. We can just store the previous value in a variable.
Code
public int maxProfit(int[] prices) {
// edge cases
if (prices == null || prices.length == 0) {
return 0;
}
// create memo table
int profit;
// init base case
profit = 0;
int localMin = prices[0];
// topo order
for (int i = 1; i < prices.length; i++) {
localMin = Math.min(localMin, prices[i]);
profit = Math.max(profit, prices[i] - localMin);
}
// answer
return memo[memo.length - 1];
}
