# 121. Best Time to Buy and Sell Stock I
## Level - Easy
## Question
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
## Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minPrice = float('inf')
        profit = 0
        for i in range(len(prices)):
            if prices[i] < minPrice:
                minPrice = prices[i] 
            else:
                profit = max(profit, prices[i]-minPrice)
        return profit
        

# 121. Best Time to Buy and Sell Stock II
## Level - Easy
## Question
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
## Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                profit += prices[i] - prices[i-1]
        return profit

# 121. Best Time to Buy and Sell Stock III
## Level - Hard
## Question
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/submissions/
### Thought 1 - Dynamic Programming
General solution. See 188.

### Thought 2 - Best solution
定義:
buy1: 第一次買的最低買進價格 => buy1 = min(buy1, prices[i])
profit1: 第一次賣的最高獲利 => profit1 = max(profit1, prices[i]-buy1)

buy2: 第二次買進的最低買進價格 => buy2 = min(buy2, prices[i]-profit1) *意義為拿第一次賺得錢來進行投資第二次買進!!!*
profit2: 第二次賣的最高獲利 => profit2 = max(profit2, prices[i]-buy2) 此值為答案

值得注意的是buy2的計算方式, 清楚的瞭解其意義才能懂為何其為答案, 另一方面來說, buy2利用了profit1 來找出 "全場第二小的值"

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy1, buy2 = float('inf'), float('inf')
        profit1, profit2 = 0, 0
        for i in range(len(prices)):
            buy1 = min(buy1, prices[i])
            profit1 = max(profit1, prices[i]-buy1)
            buy2 = min(buy2, prices[i]-profit1) # Re-investing
            profit2 = max(profit2, prices[i]-buy2)
        return profit2
    

Ref: https://www.youtube.com/watch?v=ykQ6WFuqQfE

# 188. Best Time to Buy and Sell Stock IV
## Level Hard
## Question
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

## Thought 1 - Dynamic Programming
General solution

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        
        if n==0 or k==0:
            return 0
        # Many trasactions can be done.
        # Back to Best Time to Buy and Sell Stock II
        if 2*k > n:
            profits = 0
            for i in range(1, n):
                if prices[i] > prices[i-1]:
                    profits += prices[i] - prices[i-1]
            return profits
        
        # profits['prices item']['transation times']['holding stock']
        # hoding stock = {0 means having no stock, 1 means having stock} 
        profits = [[[float('-inf')]*2 for _ in range(k+1)] for _ in range(n)]
        
        profits[0][0][0] = 0
        profits[0][1][1] = -prices[0] # buy the stock
        
        for i in range(1,n):
            for j in range(k+1):
                profits[i][j][0] = max(profits[i-1][j][0], # Last time, still empty hands 
                                    profits[i-1][j][1]+prices[i]) # Last time, selling stock
                if j>0:
                    profits[i][j][1] = max(profits[i-1][j][1], # Last time, still hold stock 
                                        profits[i-1][j-1][0]-prices[i]) # Last time, buying stock
        
        res = max(profits[n-1][j][0] for j in range(k+1))
        return res
        

### C++ Implementation

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        auto len = prices.size();
        if(len == 0 || k == 0)
            return 0;
        int profits[len][k+1][2];
        memset( profits, -10000, len*(k+1)*2*sizeof(int) );
        profits[0][0][0] = 0;
        profits[0][1][1]= -prices[0];
        for(int i=1;i<len;++i){
            for(int j=0;j<k+1;++j){
                profits[i][j][0] = max(profits[i-1][j][0], profits[i-1][j][1] + prices[i]);
                if(j>0)
                    profits[i][j][1] = max(profits[i-1][j][1], profits[i-1][j-1][0] - prices[i]);
            }
        }
        int max_v = INT_MIN;
        for(int j=0;j<k+1;++j){
            max_v = max(max_v, profits[len-1][j][0]);
        }
        return max_v;
    }
};

### Thought 2 - DP + Reducing Space

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        
        if n==0 or k==0:
            return 0
        # Many trasactions can be done.
        # Back to Best Time to Buy and Sell Stock II
        if 2*k > n:
            profits = 0
            for i in range(1, n):
                if prices[i] > prices[i-1]:
                    profits += prices[i] - prices[i-1]
            return profits
        
        # profits['transation times']['holding stock']
        # hoding stock = {0 means having no stock, 1 means having stock} 
        profits = [[float('-inf')]*2 for _ in range(k+1)]
        
        profits[0][0] = 0
        profits[1][1] = -prices[0] # buy the stock
        
        for i in range(1,n):
            prvProfits = copy.copy(profits)
            for j in range(k+1):
                profits[j][0] = max(prvProfits[j][0], # Last time, still empty hands 
                                    prvProfits[j][1]+prices[i]) # Last time, selling stock
                if j>0:
                    profits[j][1] = max(prvProfits[j][1], # Last time, still hold stock 
                                        prvProfits[j-1][0]-prices[i]) # Last time, buying stock
        
        res = max(profits[j][0] for j in range(k+1))
        return res
        

TC: O(nk), n = prices length, k = transaction times

# 309. Best Time to Buy and Sell Stock with Cooldown
## Level - Medium
## Question
## Thought - DP

sell[i] = max{sell[i - 1], buy[i-1] + prices[i]}
buy[i] = max{buy[i-1], sell[i-2] - prices[i]}
Need to be careful out of range.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        
        if n < 2:
            return 0
        
        holdProfits = [float('-inf') for _ in range(n)]
        sellProfits = [float('-inf') for _ in range(n)]
        
        holdProfits[0] = -prices[0]
        sellProfits[0] = 0
        
        holdProfits[1] = max(holdProfits[0], -prices[1])
        sellProfits[1] = max(sellProfits[0], holdProfits[0] + prices[1])
    
        
        for i in range(2, n):
            holdProfits[i] = max(holdProfits[i-1], sellProfits[i-2] - prices[i])
            sellProfits[i] = max(sellProfits[i-1], holdProfits[i-1] + prices[i])
        
        return sellProfits[n-1]

TC: O(n), n is length of prices
SC: O(n), n is length of prices

This still can be optimized to Space complexity is O(1) because the result[i] is relative with to result[n-2]. So we can use variable to replace list.