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.

max_profit.cpp

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        return maxProfit(prices, 0, prices.size());
    }
private:
    int maxProfit(vector<int> &prices, int lo, int hi) {
        if (hi - lo < 2) return 0;
        
        int mid = lo + (hi - lo) / 2;
        int left = maxProfit(prices, lo, mid);
        int right = maxProfit(prices, mid, hi);
        
        int buy = prices[lo];
        for (int i = lo + 1; i < mid; i++) {
            if (prices[i] < buy) buy = prices[i];
        }
        
        int sell = prices[mid];
        for (int i = mid + 1; i < hi; i++) {
            if (prices[i] > sell) sell = prices[i];
        }
        
        if (sell > buy) {
            int profit = sell - buy;
            return max(left, max(profit, right));
        } else {
            return max(left, right);
        }
    }
};

Another solution is iterating over the array from left right, with the current element as sell price. Then for each sell price, find in prior days for a minimum buy price -- with a min-heap takesO(log N) of time to find a minimum price. The overall run time is also O(N log N) as the divide and conquer solution above.