Divide and conquer solution, maybe it's not the best :-);


  • 1
    M
    class SolutionDivideConque {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.size() == 0) return 0;
            return profit(prices, 0, prices.size() - 1);
        }
    private:
        int profit(vector<int> &prices, int l, int r){
            if(l == r) return 0;
            int mid = l + ((r - l) >> 1);
            int lv = profit(prices, l, mid);
            int rv = profit(prices, mid + 1, r);
            vector<int>::iterator min_itr = min_element(std::begin(prices) + l, std::begin(prices) + mid + 1);
            vector<int>::iterator max_itr = max_element(std::begin(prices) + mid + 1, std::begin(prices) + r + 1);
            int diff = *max_itr - *min_itr;
            return lv > rv ?  (diff > lv ? diff : lv) : (diff > rv ? diff : rv);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.