Best Time to Buy and Sell Stock - Java Solution

1. Introduction

This blog post explores a common problem in financial computing and algorithmic trading, known as the "Best Time to Buy and Sell Stock" problem. The challenge lies in maximizing profit from a single stock trade, given the stock price for each day. This problem is a classic example of finding the maximum difference between two elements in an array where the larger element comes after the smaller one.

Problem

Given an array prices where prices[i] represents the price of a given stock on the ith day, the task is to find the maximum profit that can be achieved by buying on one day and selling on a future day. If no profit can be made, the function should return 0.

2. Solution Steps

1. Initialize two variables, minPrice to store the minimum stock price encountered so far and maxProfit to store the maximum profit that can be made.

2. Iterate through the array prices.

3. Update minPrice to be the minimum of the current element and minPrice.

4. Calculate the profit for the current day by subtracting minPrice from the current price.

5. Update maxProfit to be the maximum of the current maxProfit and the profit calculated in step 4.

6. Return the value of maxProfit after completing the iteration.

3. Code Program

public class BestTimeToBuyAndSellStock {
    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices)); // Test the function
    }

    // Function to find the maximum profit
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }

        return maxProfit;
    }
}

Output:

5

Explanation:

1. maxProfit: This function calculates the maximum profit that can be achieved from a single stock transaction.

2. It initializes minPrice to a very high value and maxProfit to 0.

3. As it iterates through the prices array, it keeps track of the lowest price seen so far and calculates the profit for each day.

4. The function updates maxProfit whenever it finds a higher profit than what was previously calculated.

5. The logic ensures that the buy action (represented by minPrice) always occurs before the sell action on a future day.

6. After iterating through all prices, maxProfit holds the highest possible profit, or 0 if no profitable transaction is possible.

7. This approach efficiently solves the problem by iterating through the array once and constantly updating the minimum price and maximum profit.