"""Leetcode 188. Best Time to Buy and Sell Stock IV
Hard

URL: https://leetcode.com/problems/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.
"""

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        pass


def main():
    # Output: 2
    prices = [2,4,1]
    k = 2
    print SolutionDp().maxProfit(k, prices)


if __name__ == '__main__':
    main()

Add lc0188_best_time_to_buy_and_sell_stock_iv.py