Problem Explanation:

You are given a list of stock prices where each element represents the price of a stock on a particular day. The goal is to determine the maximum profit you can achieve from exactly one buy-sell transaction. You need to buy the stock before selling it, meaning the “buy” day must be earlier than the “sell” day.

Steps to Solve:

  1. Track the minimum price: As you traverse through the list of prices, keep track of the minimum price encountered so far. This would be your optimal “buy” price.
  2. Calculate profit: For each price in the list, calculate the profit if you were to sell at that day’s price, using the minimum price observed so far.
  3. Update the maximum profit: Keep track of the maximum profit seen as you move through the prices.
  4. Edge Case: If no profit can be made (prices are continuously decreasing), the profit will be 0.

Example Walkthrough:

Example 1:

  • Prices: [7, 1, 5, 3, 6, 4]
  • Day 1: Buy at 7 (min price = 7), no profit (selling here gives 0 profit).
  • Day 2: Buy at 1 (min price = 1), sell at 5 (profit = 5 - 1 = 4).
  • Day 3: Profit would be 5 - 1 = 4, maximum profit stays 4.
  • Day 4: Profit would be 3 - 1 = 2, no update to maximum profit.
  • Day 5: Sell at 6, profit = 6 - 1 = 5, update max profit to 5.
  • Day 6: Profit would be 4 - 1 = 3, no update.

Max profit is 5.

Example 2:

  • Prices: [7, 6, 4, 3, 1]
  • The prices are continuously decreasing, so no profit can be made. Max profit is 0.

Code Examples


1. Python:

def maxProfit(prices):
    if not prices:
        return 0

    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        profit = price - min_price
        max_profit = max(max_profit, profit)

    return max_profit

# Example usage
prices = [7, 1, 5, 3, 6, 4]
print(f"Maximum profit: {maxProfit(prices)}")

2. Java:

public class StockProfit {
    public static int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;

        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;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("Maximum profit: " + maxProfit(prices));
    }
}

3. C++:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;

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

    return maxProfit;
}

int main() {
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    cout << "Maximum profit: " << maxProfit(prices) << endl;
}

4. JavaScript:

function maxProfit(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;

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

    return maxProfit;
}

// Example usage
const prices = [7, 1, 5, 3, 6, 4];
console.log("Maximum profit:", maxProfit(prices));

5. C#:

using System;

class StockProfit {
    public static int MaxProfit(int[] prices) {
        int minPrice = int.MaxValue;
        int maxProfit = 0;

        foreach (int price in prices) {
            minPrice = Math.Min(minPrice, price);
            maxProfit = Math.Max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }

    static void Main() {
        int[] prices = {7, 1, 5, 3, 6, 4};
        Console.WriteLine("Maximum profit: " + MaxProfit(prices));
    }
}

Time and Space Complexity:

  • Time Complexity: O(n), where n is the number of days (or the length of the array). We only traverse the list once.
  • Space Complexity: O(1), since we are using a few extra variables and not any additional data structures.
See also  Given two sorted arrays, find the median of the combined sorted array.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *