Easy understanding C++ solution


  • 6
    B
    class Solution {
    public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0) return 0;
        vector<int> min_p(n), max_p(n);
        min_p[0] = prices[0];
        for(int i = 1; i < n; i ++) min_p[i] = min(min_p[i-1], prices[i]);
        max_p[n-1] = prices[n-1];
        for(int i = n - 2; i >= 0; i --) max_p[i] = max(max_p[i+1], prices[i]);
        
        int ret = 0;
        int tmp = 0;
        for(int i = 0; i < n; i ++){
            tmp = max(tmp, prices[i] - min_p[i]);
            ret = max(ret, tmp + max_p[i] - prices[i]);
        }
        return ret;
    }
    

    };


  • 0
    B

    correct me if I'm wrong. With this solution, there might be a case where sell and buy can happen at the same price ( for same index of i)?


  • 0
    L

    yes, I think this is allowed in this problem setting


Log in to reply
 

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