188. Best Time to Buy and Sell Stock IV

Partho Biswas · Partho Biswas · commit 1f47b396036d · 2019-11-12T02:21:01.000+06:00
diff --git a/README.md b/README.md
@@ -305,8 +305,8 @@ I have solved quite a number of problems from several topics. See the below tabl
 |14| [1066. Campus Bikes II](https://leetcode.com/problems/campus-bikes-ii/)| [Python](leetcode.com/python/1066_Campus_Bikes_II.py)|  | Medium |📌 TODO: Backtracking solution is getting TLE. Solve it and implement it with DP also |
 |15| [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)| [Python](leetcode.com/python/121_Best_Time_to_Buy_and_Sell_Stock.py)| [Vid 1](https://codinginterviewclass.com/courses/coding-interview-class/lectures/12305111) | Easy | Fundamental |
 |16| [122. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)| [Python](leetcode.com/python/122_Best_Time_to_Buy_and_Sell_Stock_II.py)| [Video 01](https://www.youtube.com/watch?v=blUwDD6JYaE)| Easy | Fundamentals |
-|17| [123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)| [Python](leetcode.com/python/123_Best_Time_to_Buy_and_Sell_Stock_III.py)| [Vid 1](https://www.youtube.com/watch?v=oDhu5uGq_ic&t=2s), [Vid 2](https://www.youtube.com/watch?v=Pw6lrYANjz4) | Hard | Fundamental |
-|18| [188. Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)| [Python](leetcode.com/python/122_Best_Time_to_Buy_and_Sell_Stock_II.py)| --- | Hard | Fundamentals |
+|17| [123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)| [Python](leetcode.com/python/123_Best_Time_to_Buy_and_Sell_Stock_III.py)| **[Vid 1](https://www.youtube.com/watch?v=oDhu5uGq_ic&t=2s), [Vid 2](https://www.youtube.com/watch?v=Pw6lrYANjz4)** | Hard | Fundamental |
+|18| [188. Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)| [Python](leetcode.com/python/188_Best_Time_to_Buy_and_Sell_Stock_IV.py)| **[Vid 1](https://www.youtube.com/watch?v=oDhu5uGq_ic&t=2s), [Vid 2](https://www.youtube.com/watch?v=Pw6lrYANjz4)** | Hard | Fundamentals |
 |19| [309. Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)| [Python](leetcode.com/python/309_Best_Time_to_Buy_and_Sell_Stock_with_Cooldown.py)| --- | Medium | Fundamental |
 |20| [714. Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)| [Python](leetcode.com/python/121_Best_Time_to_Buy_and_Sell_Stock.py)| --- | Medium | Fundamental |
 
diff --git a/leetcode.com/python/188_Best_Time_to_Buy_and_Sell_Stock_IV.py b/leetcode.com/python/188_Best_Time_to_Buy_and_Sell_Stock_IV.py
@@ -0,0 +1,51 @@
+class Solution(object):
+    def maxProfit(self, k, prices):
+        """
+        :type k: int
+        :type prices: List[int]
+        :rtype: int
+        """
+        return self.maxProfitWithKTransaction(prices, k)
+
+
+    # # This solution is getting "Memory Limit Exceeded"
+    # def maxProfitWithKTransaction(self, prices, k):
+    #     if not prices:
+    #         return 0
+    #     profits = [[0 for d in prices] for t in range(k + 1)]
+    #     for t in range(1, k + 1):
+    #         maxThusFar = float('-inf')
+    #         for d in range(1, len(prices)):
+    #             maxThusFar = max(maxThusFar, profits[t - 1][d - 1] - prices[d - 1])
+    #             profits[t][d] = max(profits[t][d - 1], maxThusFar + prices[d])
+    #     return profits[-1][-1]
+    #
+    #
+    # Updated implementation to avoid "Memory Limit Exceeded". But yet "Memory Limit Exceeded"
+    def maxProfitWithKTransaction(self, prices, k):
+        if not prices or k <= 0:
+            return 0
+        evenProfits = [0 for d in prices]
+        oddProfits = [0 for d in prices]
+        for t in range(1, k + 1):
+            maxThusFar = float('-inf')
+            if t % 2 == 1:
+                currentProfits = oddProfits
+                previousProfits = evenProfits
+            else:
+                currentProfits = evenProfits
+                previousProfits = oddProfits
+            for d in range(1, len(prices)):
+                maxThusFar = max(maxThusFar, previousProfits[d - 1] - prices[d - 1])
+                currentProfits[d] = max(currentProfits[d - 1], maxThusFar + prices[d])
+        return evenProfits[-1] if t % 2 == 0 else oddProfits[-1]
+
+
+
+
+sol = Solution()
+# input = [3,2,6,5,0,3]
+input = [5,11,3,50,60,90]
+k = 2
+output = sol.maxProfit(k, input)
+print('Res: ', output)
