Best time to Buy and sell stock I, II, II, IV

XXX. Best Time to Buy and Sell Stock Variations

Dynamic Programming

Greedy

Array

Problem Statement:

Implement solutions to the "Best Time to Buy and Sell Stock" problem, focusing on various scenarios:

• Maximizing profit with one transaction.
• Maximizing profit with unlimited transactions.
• Maximizing profit with at most two transactions.
• Maximizing profit with at most k transactions.

Algorithms:

Scenario I: Single Transaction

Use a single pass to track the minimum price and calculate the maximum profit:

1. Iterate through the prices array.
2. Track the minimum price encountered so far.
3. Update the maximum profit as the difference between the current price and the minimum price.

Scenario II: Unlimited Transactions

Use a greedy approach to sum up all increasing price differences:

1. Iterate through the prices array starting from the second day.
2. Whenever the current price is higher than the previous day's price, add the difference to the profit.

Scenario III: At Most Two Transactions

Use dynamic programming to track the best profit after each transaction:

1. Track the minimum price and maximum profit for the first transaction.
2. Use the profit from the first transaction to adjust the cost for the second transaction.
3. Track the maximum profit for the second transaction.

Scenario IV: At Most k Transactions

Use dynamic programming to generalize the solution to handle k transactions:

1. Initialize arrays to track the profit and cost for each transaction.
2. Iterate through the prices array, updating the cost and profit for each transaction.

Complexity:

• Scenario I: O(n) time, O(1) space.
• Scenario II: O(n) time, O(1) space.
• Scenario III: O(n) time, O(1) space.
• Scenario IV: O(k * n) time, O(k) space.

Java Implementations:

Scenario I: Single Transaction

public int maxProfit(int[] prices) {
    int min = Integer.MAX_VALUE;
    int profit = 0;

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

    return profit;  
}

Scenario II: Unlimited Transactions

public int maxProfit(int[] prices) {
    int profit = 0;

    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) 
            profit += prices[i] - prices[i - 1]; 
    }
    return profit;
}

Scenario III: At Most Two Transactions

public int maxProfit(int[] prices) {
    int t1Cost = Integer.MAX_VALUE, 
        t2Cost = Integer.MAX_VALUE;
    int t1Profit = 0,
        t2Profit = 0;

    for (int price : prices) {
        // the maximum profit if only one transaction is allowed
        t1Cost = Math.min(t1Cost, price);
        t1Profit = Math.max(t1Profit, price - t1Cost);
        // reinvest the gained profit in the second transaction
        t2Cost = Math.min(t2Cost, price - t1Profit);
        t2Profit = Math.max(t2Profit, price - t2Cost);
    }

    return t2Profit;
}

Scenario IV: At Most k Transactions

public int maxProfit(int k, int[] prices) {
    if (k == 0) return 0;
    
    int[] profit = new int[k+1];
    int[] cost = new int[k+1];

    profit[0] = 0;
    Arrays.fill(cost, Integer.MAX_VALUE);
    
    for (int price: prices) {
        for (int i = 0; i < k; i++) {
            cost[i+1] = Math.min(cost[i+1], price - profit[i]);
            profit[i+1] = Math.max(profit[i+1], price - cost[i+1]);
        }
    }
    return profit[k];
}