Best Time to Buy and Sell Stock

Problem

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

You may choose a single day to buy one NeetCoin and choose a different day in the future to sell it.

Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.

Examples

Example 1:

Input: prices = [10,1,5,6,7,1]

Output: 6

Explanation: Buy prices[1] and sell prices[4], profit = 7 - 1 = 6.

Example 2:

Input: prices = [10,8,7,5,2]

Output: 0

Explanation: No profitable transactions can be made, thus the max profit is 0.

Constraints

• 1 <= prices.length <= 100
• 0 <= prices[i] <= 100

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Solution

We loop over days which is the sell day. We start by buying on day 0. For each potential sell day, we check if we have a new max profit, and update the buy price (lowest price seen).

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // i tracks the sell day
        // while walking, we track min value as our buy price
        int buy_price = prices[0];
        int max_profit = 0;
        for (std::size_t i = 0; i < prices.size(); ++i) {
            auto profit = prices[i] - buy_price;
            max_profit = std::max(profit, max_profit);
            buy_price = std::min(prices[i], buy_price);
        }
        return max_profit;
    }
};