Best Time To Buy And Sell Stock With Cooldown Problem


Description

LeetCode Problem 309.

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

  • After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

1
2
3
Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:

1
2
Input: prices = [1]
Output: 0

Constraints:

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProfit(vector<int>& prices) {
	    vector<vector<int>> dp(prices.size()+2, vector<int>(2));
	    for(int i=prices.size()-1; i>=0; i--){
	        for(int j=0; j<=1; j++){
	            if(j){
	                dp[i][j] = max(-prices[i]+dp[i+1][0], dp[i+1][1]);
	            }
	            else{
	                dp[i][j] = max(prices[i]+dp[i+2][1], dp[i+1][0]);
	            }
	        }
	    }
	    return dp[0][1];
	}
};




Related Posts

Count Numbers With Unique Digits Problem

LeetCode 357. Given an integer n, return the count of...

Combination Sum IV Problem

LeetCode 377. Given an array of distinct integers nums and...

Coin Change Problem

LeetCode 322. You are given an integer array coins representing...

Burst Balloons Problem

LeetCode 312. You are given n balloons, indexed from 0...

Best Time To Buy And Sell Stock With Cooldown Problem

LeetCode 309. You are given an array prices where prices[i]...

Maximum Product Subarray Problem

LeetCode 152. Given an integer array nums, find a contiguous...