# Buy and Sell Stock

## 121 I

You can only sell and buy once 1. mantain a `profit` and `low` int

## 122 II

You can buy and sell many times 1. greedy algo 2. if profitable, add on

```java
public int maxProfit(int[] prices) {
    int profit = 0;
    for(int i=1; i<prices.length; i++){
        if(prices[i] - prices[i-1] > 0){
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
}
```

## 123 III

You can only buy and sell twice 1. DP

```java
public int maxProfit(int[] prices) {
    int buy1 = - prices[0], buy2 = - prices[0];
    int sell1 = 0, sell2 = 0;

    for (int i=1; i<prices.length; i++){
    //  buy1每天都跟新購買比較
        buy1 = Math.max(buy1, - prices[i]);          // max profit of first buy
        sell1 = Math.max(sell1, buy1 + price[i]);   // max profit of first sell
        buy2 = Math.max(buy2, sell1 - price[i]);    // max profit of second buy
        sell2 = Math.max(sell2, buy2 + price[i]);   // max profit of second sell
    }    
    return sell2;
}
```

## 188 IV

You can buy and sell for k times

* Hold stock and unhold stock tables
* State: 1. hold\[i]\[j]: the max profit in ith day and j transaction with holding stock 2. unhold\[i]\[j]: the max profit in ith day and j transaction without holding stock
* Func: 1. hold\[i]\[j] = max(hold\[i-1]\[j], unhold\[i-1]\[j]-price\[i]) 2. unhold\[i]\[j] = max(unhold\[i-1]\[j], hold\[i-1]\[j-1]+ price\[i])
* Init: hold\[0]\[0-k] = - price\[0], hold\[i]\[0] = max(hold\[i-1]\[0], -price\[i])
* Ans: unhold\[len]\[k]

```java
public int maxProfit(int k, int[] prices) {
    int len = prices.length;
    if (k >= len/2) return helper(prices);

    // the max profit in ith day and k transaction with holding stock
    int[][] hold = new int[len][k+1];
    // the max profit in ith day and k transaction without holding stock
    int[][] unhold = new int[len][k+1];

    // init
    for(int j=0; j<=k; j++){
        hold[0][j] = -prices[0];
    }

    for(int i=1; i<len; i++){
        hold[i][0] = Math.max(hold[i-1][0], -prices[i]);
    }

    // func
    for(int i=1; i<len; i++){
        for(int j=1; j<=k; j++){
            hold[i][j] = Math.max(hold[i-1][j], unhold[i-1][j] - prices[i]);
            unhold[i][j] = Math.max(unhold[i-1][j], hold[i-1][j-1] + prices[i]);
        }
    }
    return unhold[len-1][k];
}

private int helper(int[] prices){
    int profit = 0;
    for(int i=1; i<prices.length; i++){
        if(prices[i] - prices[i-1] > 0){
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
    }
```

## 714 With transaction fee

You can buy and sell many times

```java
public int maxProfit(int[] prices, int fee) {
    // 2 situations: buy and sell

    int buy = -prices[0];
    int sell = 0;

    for (int i=1; i<prices.length; i++){
        buy = Math.max(buy, sell - prices[i]);
        sell = Math.max(sell, buy + prices[i] - fee);
    }
    return sell;
}
```

## 309 With 1 day cool down

You can buy and sell many times

* Func: buy\[i] = max(buy\[i-1], sell\[i-2]-price\[i]), sell\[i] = max(sell\[i-1], buy\[i-1]+price\[i])
* O(n) space

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

    int[] buy = new int[prices.length];
    int[] sell = new int[prices.length];
    buy[0] = -prices[0];

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

* O(1) space

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

    int buy = -prices[0];
    int preSell = 0;
    int curSell = 0;

    for(int i=1; i<prices.length; i++){
        int tmp = curSell;
        buy = Math.max(buy, preSell - prices[i]);
        curSell = Math.max(curSell, buy + prices[i]);
        preSell = tmp;
    }
    return curSell;
}
```


---

# 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://netjimmy.gitbook.io/code-interview-note/array/buy-and-sell-stock.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.