6.2 Jash's Stock Trading Adventure
After successfully navigating the complex course prerequisite system at Thadomal Shahani Engineering College, Jash decided to use his algorithmic skills for something more lucrative—stock trading!
Jash has been tracking a particular stock for several days and has predictions for its daily prices. Being a smart trader, he knows he can maximize his profit by buying and selling multiple times. However, there's a catch: the stock exchange has a cooldown rule. After selling a stock, Jash cannot buy it again the very next day—he must wait for one day (cooldown period) before making another purchase.
Jash wants to maximize his profit, but he's not sure what the optimal strategy is. Can you help him figure out the maximum profit he can achieve?
Constraints
1 <= n <= 5000
0 <= pᵢ <= 1000
Input Format
The first line contains a single integer n 1 <= n <= 5000 the number of days Jash has price predictions for.
The second line contains n space-separated integers p₁, p₂, ..., pₙ 0 <= pᵢ <= 1000 the predicted stock prices for each day.
Output Format
Print a single integer — the maximum profit Jash can achieve following the cooldown rule.
You may complete as many transactions as you like (buy one and sell one share multiple times)
After you sell your stock, you cannot buy stock on the next day (cooldown of 1 day)
You may not engage in multiple transactions simultaneously (you must sell the stock before you buy again)
Example 1
Input:
5
1 2 3 0 2
Output:
3
Explanation:
The optimal strategy is: [buy, sell, cooldown, buy, sell]
Day 1 Buy at price 1
Day 2 Sell at price 2 (profit 1
Day 3 Cooldown (cannot buy)
Day 4 Buy at price 0
Day 5 Sell at price 2 (profit 2
Total profit 1 2 3
Example 2
Input:
1
1
Output:
0
Explanation:
With only one day, no transaction can be completed, so the profit is 0.
Example 3
Input:
5
1 2 4 2 5
Output:
6
Explanation:
The optimal strategy is: [buy, sell, cooldown, buy, sell]
Day 1 Buy at price 1
Day 2 Sell at price 2 (profit 1
Day 3 Cooldown
Day 4 Buy at price 2
Day 5 Sell at price 5 (profit 3
Total profit 1 3 4
Alternative strategy: [buy, hold, sell, cooldown, buy, sell]
Day 1 Buy at price 1
Day 2 Hold
Day 3 Sell at price 4 (profit 3
Day 4 Cooldown
Day 5 Buy at price 2
But we can't sell, so this gives profit 3
Better strategy: [buy, sell, buy, sell]
Actually, let's recalculate: buy at 1, sell at 4 (profit=3, cooldown, buy at 2, sell at 5 (profit=3, total 6)
Log In to solve the Question