# 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;
}
```
