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 <stdio.h>
2
3int maxProfit(int* prices, int pricesSize){
4 if (pricesSize == 0) return 0;
5 int hold = -prices[0], sell = 0, cooldown = 0;
6 for (int i = 1; i < pricesSize; i++) {
7 int prev_sell = sell;
8 sell = hold + prices[i];
9 hold = fmax(hold, cooldown - prices[i]);
10 cooldown = fmax(cooldown, prev_sell);
11 }
12 return fmax(sell, cooldown);
13}
14
15int main() {
16 int prices[] = {1,2,3,0,2};
17 int size = sizeof(prices)/sizeof(prices[0]);
18 printf("Max Profit: %d\n", maxProfit(prices, size));
19 return 0;
20}This C code defines a function maxProfit that takes the array of prices and its size. The dynamic programming state variables are initialized: hold representing the maximum profit holding a stock, sell for selling it, and cooldown for the situation with a cooldown period. It iterates through each price updating these states according to whether you sell, buy, or remain idle.
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.
1
The JavaScript recursive approach uses memoization to store interim results in the memo object to prevent recalculation of states, thus optimizing performance while ensuring all buy-sell possibilities are accounted for.