Best Time to Buy and Sell Stock
Say you have an array for which the i-th element is the price of a given stock on day i.
Update: linear algorithm for this problem
Traversing the entire array, keeping tracking the current min value, and upgrading the current max gap
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.
Solution:
cannot use max - min since we have to buy the stock before sell...
cannot find min first then find the max after min, since the maximum gap might be another one, for example, min might be the last element
exhaustive search costs O(n^2)
divide and conquer: find the min of the first half and the max of the last half. compare the gap, and the gaps in each half.
T(n) = 2T(n/2) + O(n) = O(nlogn)
The following code passes LeetCode online large judge
class Solution { public: int maxProfit(vector<int> &prices) { // Start typing your C/C++ solution below // DO NOT write int main() function int s = prices.size(); if(s < 2) return 0; if(s == 2) return max(prices[1]-prices[0], 0); vector<int> left_prices; vector<int> right_prices; int min = prices[0]; int max = prices[floor((s-1)/2)+1]; for(int i = 0; i < s; i++) { if(i <= floor((s-1)/2)) { left_prices.push_back(prices[i]); if(min > prices[i]) min = prices[i]; } else { right_prices.push_back(prices[i]); if(max < prices[i]) max = prices[i]; } } int left = maxProfit(left_prices); int right = maxProfit(right_prices); int gap = max - min; if(gap >= left && gap >= right) return gap; else if(left >= gap && left >= right) return left; else return right; } };
Update: linear algorithm for this problem
Traversing the entire array, keeping tracking the current min value, and upgrading the current max gap
class Solution { public: int maxProfit(vector<int> &prices) { // Start typing your C/C++ solution below // DO NOT write int main() function int min = 0; int gap = 0; for(int i = 0; i < prices.size(); i++) { if(prices[i] < prices[min]) min = i; if(prices[i] - prices[min] > gap) gap = prices[i] - prices[min]; } return gap; } };
Comments
Post a Comment