Leetcode 309 Best Time to Buy and Sell Stock with Cooldown

You are given an array prices where prices[i] is the price of a given stock on the ith 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).

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

Input: prices = [1]
Output: 0

• This question solved by Dynamic Programming.

• Soruya göre, her gün al, sat ve bekleme olmak üzere üç işlemden biri yapılabilir. Aslında bu üç durumu bir şekilde 2 durumuna dönüştürebiliriz. stoğu tutmak veya stoğu elden çıkarmak.

• Stoğu tutmak: Bugünün sonunda, Stoğu tutarsanız maksimum kâr ve bunlar iki koşul olabilir:Bugün hisseyi satın aldın yada Daha önce satın aldığınız hisseyi satmadınız.

• Stoğu elden çıkarma: Bugünün sonunda, Stoğu elinizde tutmazsanız maksimum kâr ve bunlar da iki koşul olabilir:bugün hisseyi sattın yada Son Stoğu sattıktan sonra hiç hisse almadınız

• Cevap, stok tutmadığınız zaman, maksimum kâr olmalıdır.

• Temel durumu bulun: Biri hold, diğeri unhold olarak adlandırılan iki dp listesi oluşturun. her eleman, i. günün sonundaki maksimum karı temsil eder.

• hold[0] = -prices[0] ve unhold[0] = 0 başlat

• Deseni bulun: Biri elde tutulan stok için diğeri de elde tutulmayan stok için iki model olmalıdır:

stok tutun: max(hisseyi bugün aldınız, daha önce hisseyi aldınız ama henüz satmadınız) Stoğuni serbest bırak: max(bugün hisseyi sattın, son hisseyi sattıktan sonra hiç hisse almadın)

• Cevap: unhold[L-1].

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        L = len(prices)
        hold = [0]*L #hold[i]: the ith day profit when you hold stock
        unhold = [0]*L #unhold[i]: the ith day profit when you not hold stock
        
        hold[0] = -prices[0]
        unhold[0] = 0
        
        for i in range(1,L):
            hold[i] = max(unhold[i-2]-prices[i], hold[i-1])#max(today buy in, last buy in)
            unhold[i] = max(hold[i-1]+prices[i], unhold[i-1])#max(today sell out, not sell out)
        return unhold[L-1]