Best Time to Buy and Sell Stock

Understanding the Problem

The goal is to determine the maximum profit that can be achieved by buying and selling a stock at most once.

Method 1: Brute Force Approach

This method checks all possible pairs of buy and sell prices to find the maximum profit.

#include <iostream>
using namespace std;

int maxProfitBruteForce(int prices[], int size) {
    int maxProfit = 0;
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            int profit = prices[j] - prices[i];
            if (profit > maxProfit)
                maxProfit = profit;
        }
    }
    return maxProfit;
}

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int size = sizeof(prices) / sizeof(prices[0]);
    cout << "Maximum profit: " << maxProfitBruteForce(prices, size) << endl;
    return 0;
}
            

Output:

Maximum profit: 5

Method 2: Optimized Approach

This method uses a single pass through the array to track the minimum price and maximum profit.

#include <iostream>
using namespace std;

int maxProfitOptimized(int prices[], int size) {
    int minPrice = prices[0];
    int maxProfit = 0;
    for (int i = 1; i < size; i++) {
        if (prices[i] < minPrice)
            minPrice = prices[i];
        else if (prices[i] - minPrice > maxProfit)
            maxProfit = prices[i] - minPrice;
    }
    return maxProfit;
}

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int size = sizeof(prices) / sizeof(prices[0]);
    cout << "Maximum profit: " << maxProfitOptimized(prices, size) << endl;
    return 0;
}
            

Output:

Maximum profit: 5

Method 3: Dynamic Programming Approach

This method keeps track of minimum prices and calculates profit dynamically.

#include <iostream>
using namespace std;

int maxProfitDP(int prices[], int size) {
    if (size == 0) return 0;
    int dp[size];
    dp[0] = 0;
    int minPrice = prices[0];
    for (int i = 1; i < size; i++) {
        dp[i] = max(dp[i - 1], prices[i] - minPrice);
        if (prices[i] < minPrice)
            minPrice = prices[i];
    }
    return dp[size - 1];
}

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int size = sizeof(prices) / sizeof(prices[0]);
    cout << "Maximum profit: " << maxProfitDP(prices, size) << endl;
    return 0;
}
            

Output:

Maximum profit: 5