Best Time To Buy And Sell Stock Iii - Leetcode Solution

The Problem:

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Solution:

The problem statement asks us to find the maximum profit that can be obtained from at most two transactions. Let's take a look at a few scenarios:

1. If there are no prices, return 0.
2. If there are only one or two prices, they cannot be used to make any transactions, so return 0.
3. If there are three or more prices, we need to calculate the maximum profit that can be obtained from two transactions.

We will solve the problem using dynamic programming. Let's create a 2D array dp where dp[i][j] represents the maximum profit that can be obtained by making j transactions on the first i days of the given prices array. We can fill the dp array in the following way:

1. Initialize the dp array to 0.
2. For each day i, we will calculate the maximum profit that can be obtained by making j transactions on the first i days.
3. We can calculate the profit at each day i and transaction j by finding the maximum of: a. The profit from the previous transaction j-1 and the price difference on the current day prices[i]. b. The profit from the previous day i-1 and the profit on the current day j.
4. Return dp[n-1][2], where n is the length of the prices array.

Let's take a closer look at step 3. To calculate the profit on the current day j, we can traverse the prices array backwards and find the maximum profit that can be obtained by selling the stock on the current day j and buying it on any previous day k. We can use two variables, sell and buy, to keep track of the maximum profit that can be obtained by selling the stock and buying it on any previous day.

Here is the implementation of the above solution:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n < 2) return 0;
        
        vector<vector<int>> dp(n, vector<int>(3));
        for(int j = 1; j <= 2; j++){
            int buy = dp[0][j-1] - prices[0];
            for(int i = 1; i < n; i++){
                dp[i][j] = max(dp[i-1][j], prices[i] + buy);
                buy = max(buy, dp[i][j-1] - prices[i]);
            }
        }
        return dp[n-1][2];
    }
};

Time Complexity: O(n), where n is the length of the prices array.

Space Complexity: O(n), where n is the length of the prices array. The space complexity can be further optimized to O(1) by using variables instead of a 2D array.

1