Cpp simple solution O(n)


  • 0
    C

    get the max diff. Only when min_index > max_index, reset both indices, and try to find another diff (i.e. cur_diff) which is larger than the old max diff.

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int max_i = 0, min_i = 0;
            int max_diff = 0, cur_diff = 0;
            for (int i = 1; i < prices.size(); i++) {
                if (prices[i] > prices[max_i]) {
                    max_i = i;
                    cur_diff = prices[max_i] - prices[min_i];
                    if (cur_diff > max_diff) {
                        max_diff = cur_diff;
                    }
                }
                else if (prices[i] < prices[min_i]) {
                    if (i < max_i) {
                        min_i = i;
                        max_diff = prices[max_i] - prices[min_i];
                    } else {
                        max_i = min_i = i;
                        cur_diff = 0;
                    }
                }
            }
            return max_diff;
        }
    };

Log in to reply
 

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