714. Best Time to Buy and Sell Stock with Transaction Fee

Partho Biswas · Partho Biswas · commit 2b57f0fc30ac · 2019-11-12T10:51:20.000+06:00
diff --git a/README.md b/README.md
@@ -304,11 +304,11 @@ I have solved quite a number of problems from several topics. See the below tabl
 |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 |
+|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 | More like Greedy |
 |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 |
+|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 | **Getting "Memory Limit Exceeded"** |
+|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)| **[Must Read](https://tinyurl.com/y7eaa7vk) | 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/714_Best_Time_to_Buy_and_Sell_Stock_with_Transaction_Fee.py)| **[Must Read](https://tinyurl.com/y7eaa7vk)** | Medium | More like Greedy, but DP |
 
 
 ### Bit Manipulation
diff --git a/leetcode.com/python/714_Best_Time_to_Buy_and_Sell_Stock_with_Transaction_Fee.py b/leetcode.com/python/714_Best_Time_to_Buy_and_Sell_Stock_with_Transaction_Fee.py
@@ -0,0 +1,46 @@
+class Solution(object):
+    def maxProfit(self, prices, fee):
+        """
+        :type prices: List[int]
+        :type fee: int
+        :rtype: int
+        """
+        days = len(prices)
+        totalProfit = 0
+        minimumPrice = prices[0]
+        for today in range(1, days):
+            if prices[today] < minimumPrice:
+                minimumPrice = prices[today]
+            elif minimumPrice < (prices[today] - fee):
+                totalProfit += (prices[today] - minimumPrice - fee)
+                minimumPrice = prices[today] - fee   #  https://tinyurl.com/unnnjwx  and  https://tinyurl.com/umjax4y
+        return totalProfit
+
+
+    # def maxProfit(self, prices, fee):
+    #     """
+    #     :type prices: List[int]
+    #     :type fee: int
+    #     :rtype: int
+    #     """
+    #     days = len(prices)
+    #     if days < 2:
+    #          return 0
+    #     profit = 0
+    #     minimumPrice = prices[0]
+    #     for i in range(1, days):
+    #         if prices[i] < minimumPrice:
+    #             minimumPrice = prices[i]
+    #         elif prices[i] > minimumPrice + fee:
+    #             profit += prices[i] - fee - minimumPrice
+    #             minimumPrice = prices[i] - fee
+    #     return profit
+
+
+
+
+sol = Solution()
+prices = [1,3,7,5,10,3]
+fee = 3
+output = sol.maxProfit(prices, fee)
+print('Res: ', output)
