Best Timeto Buyand Sell Stock III Algorithm

The Best Time to Buy and Sell Stock III Algorithm is an optimization problem that aims to maximize the profit that can be obtained from buying and selling stocks, with the constraint that a maximum of two transactions can be made. This algorithm falls into the dynamic programming category, as it involves breaking down a larger problem into smaller subproblems and solving them in an organized, efficient manner. The key idea behind this algorithm is to find the most profitable points in time to buy and sell stocks, in such a way that two transactions are performed to yield the highest possible profit. To implement the algorithm, we need to keep track of the minimum price to buy the stock and the maximum profit that can be made from selling it after the first transaction. Next, we need to determine the maximum profit that can be made by selling the stock after the second transaction. We can do this by iterating through the list of stock prices, keeping track of the minimum price, the maximum profit after the first transaction, and the maximum profit after the second transaction at each step. The final result will be the maximum profit obtained after the second transaction. The Best Time to Buy and Sell Stock III Algorithm is efficient and can be used to analyze stock market trends and make informed investment decisions.
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.size() < 2) {
            return 0;
        }
        int n = prices.size();
        vector<int> dp1(n, 0);
        vector<int> dp2(n, 0);
        int minval = prices[0];
        for (int i = 1; i < n; i++) {
            minval = min(minval, prices[i]);
            dp1[i] = max(dp1[i-1], prices[i] - minval);
        }
        int maxval = prices[n-1];
        for (int i = n - 2; i >= 0; i--) {
            maxval = max(maxval, prices[i]);
            dp2[i] = max(dp2[i+1], maxval - prices[i]);
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = max(result, dp1[i] + dp2[i]);
        }
        return result;
    }
};

LANGUAGE:

DARK MODE: