# 188. Best Time to Buy and Sell Stock IV

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

# Solution

Approach 1: DP -- as a sequence of separate buy and sell actions.

Approach 2: DP -- modelled for entire transactions.

# Code (Python)

Approach 1:

    def maxProfit(self, k: int, prices: List[int]) -> int:
        # select at most 2k nums, alternating neg and pos signs, so that sum is maximized
        # profit[i][j]: max profit when select j nums from the first i prices
        # profit[i][j] = max(profit[i-1][j], profit[i-1][j-1] + (-1)^j * prices[i-1])
        if k == 0 or len(prices) < 2:
            return 0
        
        if k >= len(prices) // 2:
            total = 0
            for i in range(1, len(prices)):
                total += max(0, prices[i] - prices[i-1])
            return total

        # need to initialize as neg infinity because buying yields negative profit
        profit = [[0] + [-float('inf')] * 2 * k for _ in range(len(prices) + 1)]
        for i in range(1, len(prices) + 1):
            # for the first i items, can make at most i or 2k actions
            for j in range(1, min(i, 2 * k) + 1):
                profit[i][j] = max(
                    profit[i-1][j],
                    profit[i-1][j-1] + (-1) ** j * prices[i-1]
                )
        
        return max(profit[-1])

    def maxProfit(self, k: int, prices: List[int]) -> int:
        # same idea using 1D
        # http://bookshadow.com/weblog/2015/02/18/leetcode-best-time-to-buy-and-sell-stock-iv/
        # http://www.cnblogs.com/maples7/p/4350047.html
        if 2 * k >= len(prices):
            prev = 0
            for i in range(1, len(prices)):
                prev = prev + max(0, prices[i] - prices[i-1])
            return prev

        max_prof_at_action = [0] + [-float('inf') for _ in range(2 * k)]
        for i in range(len(prices)):
            for j in range(1, min(i + 1, 2 * k) + 1):
                buy_sell = -1 if j % 2 else 1
                max_prof_at_action[j] = max(max_prof_at_action[j], max_prof_at_action[j-1] + prices[i] * buy_sell)
        # since we're doing max(..., table[i][j-1] + ...), essentially we're buying/selling then selling/buying at day i, that's why we don't need the max in the return
        return max_prof_at_action[2*k]

Approach 2:

    def maxProfit(self, k: int, prices: List[int]) -> int:
        # profit[i][k]: max profit for the first i days with at most k transactions, k <= 2i
        # profit[i][k] = max(profit[m][k-1] + max_once(m + 1, i)) for all m from 1 to i-1 (inclusive)
        # profit[i][0] = 0 for all i, profit[0][k] = -inf
        
        # the following code implements the following idea at https://pobenliu.gitbooks.io/leetcode/Best%20Time%20to%20Buy%20and%20Sell%20Stock%20IV.html
        # must_sell[i][j]: max profit for day i with at most j transactions, must sell at day i
        # max_profit[i][j]: max profit for day i with at most j transactions, can sell or hold
        
        if k >= len(prices) // 2:
            total = 0
            for i in range(1, len(prices)):
                total += max(0, prices[i] - prices[i-1])
            return total
        
        must_sell = [[0] * (k + 1) for _ in range(len(prices))]
        max_profit = [[0] * (k + 1) for _ in range(len(prices))]
        
        for i in range(1, len(prices)):
            for j in range(1, k + 1):
                must_sell[i][j] = max(
                    must_sell[i-1][j] - prices[i-1] + prices[i], # sold yesterday, then buy yesterday and sell today => hold until sell today
                    max_profit[i-1][j-1] - prices[i-1] + prices[i] # do one more transaction yesterday and today
                )
                max_profit[i][j] = max(
                    max_profit[i-1][j], # no transactions today
                    must_sell[i][j] # do a transaction today
                )
        
        return max_profit[-1][-1]

# Code (C++)

Approach 1:

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n < 2 || k < 1)
            return 0;
        int res = 0;
        if (k >= n / 2) // To prevent Memory Limit Exceeded.
        {
            for (int i = 1; i < n; ++i)
            {
                if (prices[i] > prices[i-1])
                    res += prices[i] - prices[i-1];
            }
        }
        else
        {
            vector<int> buy(k+1, INT_MIN);
            vector<int> sell(k+1, 0);
            for (int i = 0; i < n; ++i)
            {
                for (int j = 1; j <= k; ++j)
                {
                    sell[j] = std::max(sell[j], buy[j] + prices[i]);
                    buy[j] = std::max(buy[j], sell[j-1] - prices[i]);
                }
            }
            for (int i = 1; i <= k; ++i)
            {
                res = std::max(res, sell[i]);
            }
        }
        return res;
    }
};