C++: Best Time to Buy and Sell Stock

Thought Process

To maximize profit, we need to buy at the lowest price and sell at the highest price after the buy. We initialize the buy price with the first element of the array and iterate through the array. If the current price is higher than the buy price, we calculate the profit and update the global profit if this profit is greater. If the current price is lower than the buy price, we update the buy price to the current price. 

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int buy = prices[0];
        int globalProfit = 0;

        for(int i=1;i<prices.size();i++){

            int sell = prices[i];
            if(sell > buy){
                int profit = sell - buy;
                globalProfit = max(globalProfit,profit);
            }
            else{
                buy = sell;
            }
        }
        return globalProfit;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the array once, making it linear in time complexity.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, regardless of the input size.

Code copied!