123. Best Time to Buy and Sell Stock III

Partho Biswas · Partho Biswas · commit 65af29edf7a1 · 2019-11-12T00:44:29.000+06:00
diff --git a/README.md b/README.md
@@ -276,36 +276,39 @@ I have solved quite a number of problems from several topics. See the below tabl
 ### [Greedy](https://www.youtube.com/watch?v=ARvQcqJ_-NY)
 | #  | Title | Solution | Tutorial | Level | Remarks |
 | --- | --- | --- | --- | --- | --- |
-|01| [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 |
+|01| **[1055. Shortest Way to Form String](https://leetcode.com/problems/shortest-way-to-form-string/)**| [Python](leetcode.com/python/1055_Shortest_Way_to_Form_String.py)| [Art 1](https://tinyurl.com/t6xap4c), [Art 2](https://leetcode.com/problems/shortest-way-to-form-string/discuss/330938/Accept-is-not-enough-to-get-a-hire.-Interviewee-4-follow-up) | Medium | 📌 **[Check BS approach again](https://tinyurl.com/t6xap4c)** |
 |02| [1057. Campus Bikes](https://leetcode.com/problems/campus-bikes/)| [Python](leetcode.com/python/1057_Campus_Bikes.py)| [Video 01](https://www.youtube.com/watch?v=tG7GFge4-fQ), [Article 01](https://leetcode.com/problems/campus-bikes/discuss/371604/Python-Solution-Using-Dictionary-With-Explanation)| Medium | 📌 Solve [1066. Campus Bikes II](https://leetcode.com/problems/campus-bikes-ii/) using [DP](https://leetcode.com/problems/campus-bikes-ii/discuss/303471/Python-DP-vs-Backtracking-with-comments), [DFS](https://leetcode.com/problems/campus-bikes-ii/discuss/303383/Python-DFS-with-memorization) and [Priority Queue](https://leetcode.com/problems/campus-bikes-ii/discuss/303422/Python-Priority-Queue) |
 |03| [1007. Minimum Domino Rotations For Equal Row](https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/)| [Python](leetcode.com/python/Minimum_Domino_Rotations_For_Equal_Row.py)| [Official](https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/solution/), [Article 01](https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/discuss/252242/JavaC%2B%2BPython-Different-Ideas)| Medium | 📌 Hard to spot if it is a Greedy |
 |04| [406. Queue Reconstruction by Height](https://leetcode.com/problems/queue-reconstruction-by-height/)| [Python](leetcode.com/python/406_Queue_Reconstruction_by_Height.py)| [Article 1](https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89345/Easy-concept-with-PythonC%2B%2BJava-Solution), [Article 2](https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89359/Explanation-of-the-neat-Sort%2BInsert-solution) | Medium | 📌 Fundamentals |
 |05| [621. Task Scheduler](https://leetcode.com/problems/task-scheduler/)| [Python](leetcode.com/python/621_Task_Scheduler.py)| [Ex 1](https://leetcode.com/problems/task-scheduler/discuss/190390/Can-anyone-explain-to-me-what-the-problem-is-asking), [Ex 2](https://leetcode.com/problems/task-scheduler/discuss/130786/Python-solution-with-detailed-explanation), [Vid 1](https://www.youtube.com/watch?v=hVhOeaONg1Y) | Medium | 📌 Extremely tricky. Not done. Check later |
 |06| [392. Is Subsequence](https://leetcode.com/problems/is-subsequence/)| [Python](leetcode.com/python/392_Is_Subsequence.py)| [Ex 1](https://leetcode.com/problems/is-subsequence/discuss/87264/Easy-to-understand-binary-search-solution), [Ex 3](https://leetcode.com/problems/is-subsequence/discuss/87302/Binary-search-solution-for-follow-up-with-detailed-comments/144323) | Easy | 📌  |
 |07| **[55. Jump Game](https://leetcode.com/problems/jump-game/)** | [Python](leetcode.com/python/55_Jump_Game.py)| **[Official](https://leetcode.com/articles/jump-game/)** , [Art 1](https://tinyurl.com/yy9vyjyn)| Medium | 📌 **Must Check. Learned a lot** |
 |08| [45. Jump Game II](https://leetcode.com/problems/jump-game-ii/)| [Python](leetcode.com/python/45_Jump_Game_II.py)| [Vid  1](https://www.youtube.com/watch?v=cETfFsSTGJI), [Vid 2](https://www.youtube.com/watch?v=jH_5ypQggWg), [Vid 3](https://www.youtube.com/watch?v=vBdo7wtwlXs), [Art 1](https://tinyurl.com/yalsno6r) | Hard | 📌  |
-|09| **[1055. Shortest Way to Form String](https://leetcode.com/problems/shortest-way-to-form-string/)**| [Python](leetcode.com/python/1055_Shortest_Way_to_Form_String.py)| [Art 1](https://tinyurl.com/t6xap4c), [Art 2](https://leetcode.com/problems/shortest-way-to-form-string/discuss/330938/Accept-is-not-enough-to-get-a-hire.-Interviewee-4-follow-up) | Medium | 📌 **[Check BS approach again](https://tinyurl.com/t6xap4c)** |
 
 
 ### [Dynamic Programming](https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews)
 | #  | Title | Solution | Tutorial | Level | Remarks |
 | --- | --- | --- | --- | --- | --- |
-|01| [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)|
-|02| [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 |
-|03| [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/submissions/)| [Python](leetcode.com/python/53_Maximum_Subarray.py)|
-|04| [518. Coin Change 2](https://leetcode.com/problems/coin-change-2/)| [Python](leetcode.com/python/518_Coin_Change_2.py)|
-|05| [322. Coin Change](https://leetcode.com/problems/coin-change/solution/)| [Python](leetcode.com/python/322_Coin_Change.py)|
-|06| [72. Edit Distance](https://leetcode.com/problems/edit-distance/)| [Python](leetcode.com/python/72_Edit_Distance.py)| [Video 01](https://tinyurl.com/y4a7ohay)|
-|07| [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)| [Python](leetcode.com/python/70_Climbing_Stairs.py)|
-|08| [96. Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/)| [Python](leetcode.com/python/96_Unique_Binary_Search_Trees.py)| [Video 01](https://www.youtube.com/watch?v=GgP75HAvrlY), [Video 02](https://www.youtube.com/watch?v=JrTKVvYhT_k)|
-|09| [95. Unique Binary Search Trees II](https://leetcode.com/problems/unique-binary-search-trees-ii/)| [Python](leetcode.com/python/95_Unique_Binary_Search_Trees_II.py)|
-|10| [221. Maximal Square](https://leetcode.com/problems/maximal-square/)| [Python](leetcode.com/python/221_Maximal_Square.py)| [Video 01](https://www.youtube.com/watch?v=_Lf1looyJMU), [Video 02](https://www.youtube.com/watch?v=FO7VXDfS8Gk)|
-|11| [85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)| [Python](leetcode.com/python/85_Maximal_Rectangle.py)| [Video 01](https://www.youtube.com/watch?v=g8bSdXCG-lA)|
-|12| [42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)| [Python](leetcode.com/python/42_Trapping_Rain_Water.py)| [Article 01](https://leetcode.com/problems/trapping-rain-water/solution/)| Hard | 📌 Check stack and 2 pointers based solutions |
-|13| [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)| [Python](leetcode.com/python/300_Longest_Increasing_Subsequence.py)| [Article 01](https://www.algoexpert.io/questions/Longest%20Increasing%20Subsequence)| Medium | 📌 Need to check Binary Search approach, which is a lot harder |
-|14| [1143. Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/)| [Python](leetcode.com/python/1143_Longest_Common_Subsequence.py)| --- | Medium | 📌 Classic DP |
-|15| [5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)| [Python](leetcode.com/python/5_Longest_Palindromic_Substring.py)| --- | Medium | 📌 Classic DP |
-|16| [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 |
+|01| [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/submissions/)| [Python](leetcode.com/python/53_Maximum_Subarray.py)|
+|02| [518. Coin Change 2](https://leetcode.com/problems/coin-change-2/)| [Python](leetcode.com/python/518_Coin_Change_2.py)|
+|03| [322. Coin Change](https://leetcode.com/problems/coin-change/solution/)| [Python](leetcode.com/python/322_Coin_Change.py)|
+|04| [72. Edit Distance](https://leetcode.com/problems/edit-distance/)| [Python](leetcode.com/python/72_Edit_Distance.py)| [Video 01](https://tinyurl.com/y4a7ohay)|
+|05| [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)| [Python](leetcode.com/python/70_Climbing_Stairs.py)|
+|06| [96. Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/)| [Python](leetcode.com/python/96_Unique_Binary_Search_Trees.py)| [Video 01](https://www.youtube.com/watch?v=GgP75HAvrlY), [Video 02](https://www.youtube.com/watch?v=JrTKVvYhT_k)|
+|07| [95. Unique Binary Search Trees II](https://leetcode.com/problems/unique-binary-search-trees-ii/)| [Python](leetcode.com/python/95_Unique_Binary_Search_Trees_II.py)|
+|08| [221. Maximal Square](https://leetcode.com/problems/maximal-square/)| [Python](leetcode.com/python/221_Maximal_Square.py)| [Video 01](https://www.youtube.com/watch?v=_Lf1looyJMU), [Video 02](https://www.youtube.com/watch?v=FO7VXDfS8Gk)|
+|09| [85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)| [Python](leetcode.com/python/85_Maximal_Rectangle.py)| [Video 01](https://www.youtube.com/watch?v=g8bSdXCG-lA)|
+|10| [42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)| [Python](leetcode.com/python/42_Trapping_Rain_Water.py)| [Article 01](https://leetcode.com/problems/trapping-rain-water/solution/)| Hard | 📌 Check stack and 2 pointers based solutions |
+|11| [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)| [Python](leetcode.com/python/300_Longest_Increasing_Subsequence.py)| [Article 01](https://www.algoexpert.io/questions/Longest%20Increasing%20Subsequence)| Medium | 📌 Need to check Binary Search approach, which is a lot harder |
+|12| [1143. Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/)| [Python](leetcode.com/python/1143_Longest_Common_Subsequence.py)| --- | Medium | 📌 Classic DP |
+|13| [5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)| [Python](leetcode.com/python/5_Longest_Palindromic_Substring.py)| --- | Medium | 📌 Classic DP |
+|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 |
+|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 |
 
 
 ### Bit Manipulation
diff --git a/leetcode.com/python/123_Best_Time_to_Buy_and_Sell_Stock_III.py b/leetcode.com/python/123_Best_Time_to_Buy_and_Sell_Stock_III.py
@@ -0,0 +1,23 @@
+class Solution(object):
+    def maxProfit(self, prices):
+        """
+        :type prices: List[int]
+        :rtype: int
+        """
+        return self.maxProfitWithKTransaction(prices, 2)
+
+
+    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]
+
+
+
+
