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.
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

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 4 Trees and Graphs