Leetcode Study Day 5

Best Time to Buy and Sell Stock

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.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
 

Constraints:

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

My Solution

Failed to find a solution by myself. So sad. I was trying to record the index and the value for every element and compare each element’s value and index. However, I failed to solve the situation that if the last element is the smallest one and we should ignore it.

“Buy low, sell high”

The idea is to find the minimum price (the day to buy) and the maximum profit (the day to sell) while iterating through the array of prices.

In ChatGPT’s code, there is no need to record the maximum value, the only two variables are the minimum value and the max profit. In the loop, we comapre the minimum value with the current value, find who is the smallest, and find the profit between them. Then we compare the profit with the max profit, find who is the largest.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) {
            return 0; // If there are less than 2 days, you can't make a profit.
        }

        int minPrice = prices[0]; // Initialize the minimum price as the first day's price.
        int maxProfit = 0;       // Initialize the maximum profit as 0.

        for (int i = 1; i < n; ++i) {
            // Update the minimum price if a lower price is encountered.
            minPrice = min(minPrice, prices[i]);

            // Calculate the potential profit if you sell on the current day.
            int potentialProfit = prices[i] - minPrice;

            // Update the maximum profit if the potential profit is higher.
            maxProfit = max(maxProfit, potentialProfit);
        }

        return maxProfit;
    }
};

This is a smart idea and I am annoying that I didn’t think of it.