Best Time to Buy and Sell Stock

Problem

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Constraints

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

Solution

The problem Best Time to Buy and Sell Stock can be solved using a dynamic programming. Maximum profit can be achieved by subtracting minimum price until the nth day from the price of a given stock on the nth day. Minimum price until the nth day is the minimum value between the minimum price until the (n - 1)th day or the price on the nth day. One final thing to note is that when a minimum price is updated on the nth day, selling a stock on that day will never produce a maximum profit. Therefore, if ... else statement can be used for updating values for minimum price and maximum profit instead of a if ... if statement, slightly reducing the time complexity.

Implementation

class Solution
{
  public:
    int maxProfit(vector<int> &prices)
    {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        int profit = 0;
        int buy = 10001;

        for (int price : prices)
        {
            if (buy > price)
                buy = price;
            else
                profit = max(profit, price - buy);
        }

        return profit;
    }
};