NlogN solution C++


  • 0
    B
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            map<int, int> mp;
            if(prices.size()<2)
                return 0;
            for(int i=0; i<prices.size()-1; ++i){
                mp[prices[i]]++;
            }
    
            int ans=0, rmax=0, rans=0;
            for(int i=prices.size()-1; i>0; --i){
    
                int temp=mp.begin()->first;
                ans=max(ans, prices[i]-temp+rans);
                mp[prices[i-1]]--;
                if(mp[prices[i-1]]==0)
                    mp.erase(prices[i-1]);
                rmax=max(rmax, prices[i]);
                rans=max(rans, rmax-prices[i-1]);
            }
            return ans;
        }
    };

Log in to reply
 

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