Leetcode 123. Best Time to Buy and Sell Stock III (Hard) (cpp)

Leetcode 123. Best Time to Buy and Sell Stock III (Hard) (cpp)

Tag: Array, Dynamic Programming

Difficulty: Hard

/* 123. Best Time to Buy and Sell Stock III (Hard) Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). */ class Solution { public: int maxProfit(vector<int>& prices) { if (prices.size() < 2) { return 0; } vector<int> pro(prices.size()); pro[0] = 0; int buy = prices[0]; for (int i = 1; i < prices.size(); i++) { pro[i] = max(pro[i - 1], prices[i] - buy); buy = min(buy, prices[i]); } int sell = prices.back(), best = 0; for (int i = prices.size() - 2; i >= 0; i--) { best = max(best, sell - prices[i] + pro[i]); sell = max(sell, prices[i]); } return best; } };