# 309     Best Time to Buy and Sell Stock with Cooldown

## 309. [Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/)

## 1. Question

Say you have an array for which theithelement is the price of a given stock on dayi.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

* You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
* After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

**Example:**

```
Input:
 [1,2,3,0,2]

Output: 
3 

Explanation:
transactions = [buy, sell, cooldown, buy, sell]
```

## 2. Implementation

**(1) DP:**

buy\[i]表示在第i天我们买股票所获得的最大利润, buy\[i]的状态取决于两方面:

1.不买任何股票，和前一天一样

2.买第i天股票，但因为有cool down，所以第i天买股票必须要i - 2天前卖了股票后

所以状态转移方程为 buy\[i] = Math.max(buy\[i - 1], sell\[i - 2] - prices\[i])

sell\[i]表示在第i天我们卖股票所获得的最大利润, 和buy\[i]类似，sell\[i]的状态取决于两方面:

1.不卖任何股票，和前一天一样

1. 卖第i天股票，注意这里卖股票没有cooldown的限制，即前天买了股票后第二天可以卖

状态转移方程为 sell\[i] = Math.max(sell\[i - 1], buy\[i - 1] + prices\[i])

```java
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        int n = prices.length;
        int[] buy = new int[n];
        int[] sell = new int[n];

        // Initialization
        buy[0] = -prices[0];
        sell[0] = 0;

        for (int i = 1; i < n; i++) {
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
            buy[i] = Math.max(buy[i - 1], (i > 1 ? sell[i - 2] : 0) - prices[i]);
        }

        return Math.max(buy[n - 1], sell[n - 1]);
    }
}
```

## 3. Time & Space Complexity

**DP**: 时间复杂度O(n), 空间复杂度O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/309-best-time-to-buy-and-sell-stock-with-cooldown.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.