Problem:
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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 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
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution:
The brutal force approach is for each day, we iterate all the elements on its right and find the max value to calculate a profit. Finding the max value cost O(N) calculation, and since we need to calculate a profit for each day in order to find global maximum, the time complexity is O(N^2). We can apply dynamic programming to get a solution with O(N) time complexity. Instead of processing array elements from left to right, we exam the array element from right to left, and we record for each day, what is the best sell price we saw so far. Eventually, we will get an array that able to return us the best sell price for each day with cost O(1). With this array ready, we iterate the original array from left to right, use best sell price minus the buy price for that day, then get a profit. Finally, we found the global maximum profit.
class Solution {
public static void main(String...args) {
int[] arr = new int[]{7,1,5,3,6,4};
int profit = solve(arr);
System.out.println(profit);
}
public static int solve(int[] arr) { //7,6,4,3,1
if(arr.length < 2) return 0;
int[] sellMax = new int[arr.length]; //7,6,4,3,1
sellMax[arr.length - 1] = arr[arr.length - 1];
for(int i = arr.length - 2; i >= 0; i--) {
sellMax[i] = Math.max(arr[i], sellMax[i + 1]);
}
int profit = 0;
for(int i = 0; i < arr.length; i++) { //5
profit = Math.max(profit, sellMax[i] - arr[i]);
}
return profit;
}
}
public static void main(String...args) {
int[] arr = new int[]{7,1,5,3,6,4};
int profit = solve(arr);
System.out.println(profit);
}
public static int solve(int[] arr) { //7,6,4,3,1
if(arr.length < 2) return 0;
int[] sellMax = new int[arr.length]; //7,6,4,3,1
sellMax[arr.length - 1] = arr[arr.length - 1];
for(int i = arr.length - 2; i >= 0; i--) {
sellMax[i] = Math.max(arr[i], sellMax[i + 1]);
}
int profit = 0;
for(int i = 0; i < arr.length; i++) { //5
profit = Math.max(profit, sellMax[i] - arr[i]);
}
return profit;
}
}
Since we iterate the array twice, the time complexity is O(N), we need an extra array to store the best sell price for each day, the space complexity is O(N) as well.
