Buy and Sell Stock (Single Transaction) 🚀

Welcome to a fascinating journey into the world of Data Structures and Algorithms! Today, we're diving into a classic problem that's often encountered in real-world scenarios – buying and selling stocks for a single transaction.

💡 Pro Tip: Understanding this concept lays a solid foundation for more complex problems like the Knapsack Problem and Dynamic Programming.

The Problem 📝

Suppose 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 buying the stock on a certain day and selling it on another day. However, there is a catch – you can only make a single transaction.

Understanding the Concept 🎯

Let's break it down into simpler terms. Imagine you're at a grocery store where all the prices are displayed for a week. Your goal is to buy an item at the lowest possible price and sell it at the highest possible price, but you can only buy or sell it once.

To tackle this problem, we'll need to keep track of the minimum price encountered so far (to determine the best time to buy) and the maximum profit obtained so far (to keep a record of the best transaction).

Implementing the Solution ✅

Here's a simple Python solution for the problem:

python

def max_profit(prices):
    if len(prices) < 2:
        return 0

    min_price = prices[0]
    max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        elif price > min_price + max_profit:
            max_profit = price - min_price

    return max_profit

Let's go through the code:

We first check if the list contains at least two elements (since we need at least two days to make a transaction).
We initialize min_price with the first element in the array and max_profit with zero.
We then iterate through the array. If the current price is less than the min_price found so far, we update min_price. If the current price is greater than the min_price plus the current max_profit, we update max_profit.
Finally, we return the maximum profit obtained.

Putting It into Practice 📝

Let's test our function with an example:

python

prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices))  # Output: 5

In this example, we buy the stock on the 2nd day (when the price is 1) and sell it on the 4th day (when the price is 5), achieving a profit of 5.

Buy and Sell Stock (Single Transaction) 🚀

Buy and Sell Stock (Single Transaction) 🚀

The Problem 📝

Understanding the Concept 🎯

Implementing the Solution ✅

Putting It into Practice 📝

Quiz Time 🎯