Two solutions with analysis


  • 0
    Y

    Solution 1:
    You are permitted to have only transaction(buy one stock and sell the stock).
    The profit of the transaction could be divided to 2 parts:
    profit of buying the stock + profit of selling the stock.
    Therefore, you can have one variable to track the profit of buying the stock and another variable to track the profit of selling the stock.
    '''
    class Solution {
    public:
    int maxProfit(vector<int>& prices) {
    if(prices.empty()) return 0;
    int buy(INT_MIN),sell(INT_MIN);
    for(std::size_t i=0;i<prices.size();++i){
    buy = std::max(buy,0-prices[i]);
    sell = std::max(sell,prices[i] + buy);
    }
    return sell;
    }
    };
    '''

    Solution 2:
    Keep iterating the vector, for each price, calculate the current profit based on:
    current profit = current price -minimum price so far
    and compare it with the maximum profit.
    '''
    int maxProfit(vector<int>& prices) {
    int max_profit(0),min_so_far(INT_MAX);
    for(int i = 0; i < prices.size(); i++){
    min_so_far = min(min_so_far, prices[i]);
    max_profit = max(max_profit, prices[i] - min_so_far);
    }
    return max_profit;
    }
    '''


Log in to reply
 

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