Leetcode 123 Solution

This article provides solution to leetcode question 123 (best-time-to-buy-and-sell-stock-iii)
Categories:
Tags:
Access this page by simply typing in "lcs 123" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii

Solution

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> op_profit1(prices.size());
        int min_val = INT_MAX;
        for (int i = 0; i < (int)prices.size(); i++)
        {
            min_val = min(min_val, prices[i]);
            op_profit1[i] = i == 0 ? 0 : max(op_profit1[i - 1], prices[i] - min_val);
        }



        vector<int> op_profit2(prices.size() + 1);
        int max_val = INT_MIN;
        for (int i = prices.size() - 1; i >= 0; i--)
        {
            max_val = max(max_val, prices[i]);
            op_profit2[i] = i == prices.size() - 1 ? 0 : max(op_profit2[i + 1], max_val - prices[i]);
        }



        int op_profit = 0;
        for (int i = 0; i < (int)prices.size(); i++)
            op_profit = max(op_profit, op_profit1[i] + op_profit2[i + 1]);



        return op_profit;
    }
};