Dynamic Programming solution of Best Time To Buy And Sell Stock II

P-ppc · P-ppc · commit 282d670b6bf4 · 2018-11-10T21:21:49.000+08:00
diff --git a/algorithms/BestTimeToBuyAndSellStockII/README.md b/algorithms/BestTimeToBuyAndSellStockII/README.md
@@ -47,4 +47,25 @@ class Solution(object):
                 max_profit += prices[i] - prices[i - 1]
             
         return max_profit
+```
+or use Dynamic Programming like below:
+```python
+class Solution(object):
+    def maxProfit(self, prices):
+        """
+        :type prices: List[int]
+        :rtype: int
+        """
+        if len(prices) == 0:
+            return 0
+        # profit of not hold stock in i
+        not_holder = 0
+        # profit of hold stock in i, of course it's -prices[0] when i = 0
+        holder = -prices[0]
+        
+        for i in xrange(1, len(prices)):
+            not_holder = max(not_holder, prices[i] + holder)
+            holder = max(holder, not_holder - prices[i])
+        
+        return max(holder, not_holder)
 ```
