LeetCode: Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

---

We can keep record the maximum profit we can make while reading price data.

C++ Code:

/*
 * func: best_time_buy_sell
 * goal: find the maximum profit if only one trasaction permitted
 * @param prices: the prices of stock
 * return: maximum profit
 */
/*
 * keep recording the profit when reading the price data
 * complexity: time O(n), space O(1)
 */
int best_time_buy_sell(vector<int> &prices){
    int max_profit = 0;
    if(prices.size() <= 1){
        return 0;
    }
    int curr_min = prices[0];
    int curr_max = prices[0];
    for(const int &price : prices){
        //If current price is lower than the minimum
        //Reset the minimum and maximum
        //The reason for resetting the curr_max is that we
        //Can only find a higher price occuring later than
        //Current price.
        if(price < curr_min){
            curr_min = price;
            curr_max = price;
        }
        //If current price is higher than the maximum
        //Then a potential higher profit may be found
        if(price > curr_max){
            curr_max = price;
        }
        max_profit = max(max_profit, curr_max-curr_min);
    }
    
    return max_profit;
}

Python Code:

# func: find the maximum profit if only one transaction is permitted
# @param prices: daily price of the stock
# @return: maximum price
# complexity: time O(n), space O(1)
def maximum_profit(prices):
    if not prices:
        return 0
    max_profit = 0
    curr_min = prices[0]
    curr_max = prices[0]
    for price in prices:
        if price < curr_min:
            curr_min = price
            curr_max = price

        if price > curr_max:
            curr_max = price

        max_profit = max(max_profit, curr_max - curr_min)

    return max_profit