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:
- 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.
- 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.
- Update the maximum profit: Keep track of the maximum profit seen as you move through the prices.
- 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 gives0profit). - Day 2: Buy at
1(min price =1), sell at5(profit =5 - 1 = 4). - Day 3: Profit would be
5 - 1 = 4, maximum profit stays4. - 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 to5. - 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
nis 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.
