Leetcode: 121. Best Time to Buy and Sell Stock

Max Profit Problem - Coding Solution

Problem

Given an array of stock prices, find the maximum profit that can be achieved by buying and selling at different prices. You can only make one transaction (i.e., buy once and sell once).

Coding Solution

class Solution {
public:
    int maxProfit(std::vector& prices) {
        int min_price = std::numeric_limits::max();
        int max_profit = 0;
        for (int i = 0; i < prices.size(); i++) {
            if (prices[i] < min_price) {
                min_price = prices[i];
            } else if (prices[i] - min_price > max_profit) {
                max_profit = prices[i] - min_price;
            }
        }
        return max_profit;
    }
};
    

The solution is implemented in C++ and follows a greedy approach. We initialize min_price with the maximum possible value using std::numeric_limits::max(). We also initialize max_profit to zero.

We iterate through the prices array and update min_price if we encounter a smaller price. If the difference between the current price and min_price is greater than max_profit, we update max_profit accordingly.

The time complexity of this solution is O(n), where n is the length of the prices array, since we perform a single pass through the array.

Example

Consider the following array of stock prices: [7, 1, 5, 3, 6, 4]. By buying at a price of 1 and selling at a price of 6, we can achieve a maximum profit of 5.

Input:

[7, 1, 5, 3, 6, 4]

Output:

5