O(n) C++ solution


  • 0
    L
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
    
            const size_t n=prices.size();
            if (n<=1)
                return 0;
    
            
            // lowest[i] == lowest price from 0..i
            // highest[i] == highest price from i..end
            vector<int> lowest;
            vector<int> highest(n); 
            size_t i,j;
            int themin=prices[0];
            int themax=prices[n-1];
            for (i=0;i<n;i++){
                themin=min(prices[i],themin);
                lowest.push_back(themin);
                themax=max(prices[n-i-1],themax);
                highest[n-i-1]=(themax);
            }
    
            int ans=0;
            for (i=0;i<n-1;i++){
                ans=max(ans, highest[i+1]-lowest[i]);
            }
            return ans;
        }
    };

Log in to reply
 

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