Sponsored
Sponsored
This approach uses dynamic programming to track three states on each day: holding, not holding with cooldown, and not holding without cooldown. The idea is to decide the best action for any day based on the previous day's states. At each step, calculate the maximum profit for holding a stock, selling it, or being idle.
Time Complexity: O(n), where n is the number of days. Each day's prices are visited once.
Space Complexity: O(1), since only a fixed amount of extra space is used.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int maxProfit(std::vector<int>& prices) {
8 if (prices.empty()) return 0;
9 int hold = -prices[0], sell = 0, cooldown = 0;
10 for (size_t i = 1; i < prices.size(); ++i) {
11 int prev_sell = sell;
12 sell = hold + prices[i];
13 hold = std::max(hold, cooldown - prices[i]);
14 cooldown = std::max(cooldown, prev_sell);
15 }
16 return std::max(sell, cooldown);
17 }
18};
19
20int main() {
21 Solution sol;
22 std::vector<int> prices = {1, 2, 3, 0, 2};
23 std::cout << "Max Profit: " << sol.maxProfit(prices) << std::endl;
24 return 0;
25}This C++ solution uses a similar dynamic programming strategy. It maintains variables hold, sell, and cooldown which are updated everyday based on calculations from the previous day. The solution uses vectors to manage the prices and calculate profits accordingly.
This approach involves a recursive solution that tracks the profit by exploring all possible transactions. To optimize the solution, memoization is used to store and reuse results of repeated states to avoid redundant calculations.
Time Complexity: O(n), where n is the number of days. Thanks to memoization, each state is computed once.
Space Complexity: O(n), for the memoization table.
This C version uses a recursive function called solve that considers each day and whether you can buy or have to sell, using memoization for repetitive states. It attempts both buying and selling actions recursively and stores maximum profits attainable to avoid recomputation.