Update max_profit_k_transactions.py

Мето Трајковски · Мето Трајковски · commit 9c08a05c87b2 · 2019-11-27T21:36:12.000+01:00
diff --git a/Dynamic Programming/max_profit_k_transactions.py b/Dynamic Programming/max_profit_k_transactions.py
@@ -9,6 +9,7 @@
 given k transactions. Note that you can only hold 1 share of the stock at a time; in other words,
 you cannot buy more than 1 share of the stock on any given day, and you cannot buy a share of the
 stock if you are still holding another share.
+In a day, you can first sell a share and buy another after that.
 
 Input: [5, 11, 3, 50, 60, 90], 2
 Output: 93
@@ -37,8 +38,9 @@ def max_profit_with_k_transactions(prices, k):
         return 0
 
     # transaction = buy + sell (2 separate days)
-    # max transactions should be half from the days
-    k = min(k, days // 2)
+    # in a day you can sell and after that buy a share
+    # (according to this, can't exists more transactions than the number of the prices/days)
+    k = min(k, days)
     # create space optimized dp matrix
     dp = [[0 for j in range(days)] for i in range(2)]
 
@@ -51,14 +53,14 @@ def max_profit_with_k_transactions(prices, k):
 
         # the values in dp table for these days will be same
         # just ignore them, don't update them (because those combinations were tried)
-        past_days = 2 * t
+        past_days = t
         # only save the last one
         dp[curr_idx][past_days] = dp[prev_idx][past_days]
 
         for d in range(past_days + 1, days):
-            # first try to sell with the current price
+            # first try to buy with the current price
             max_prev = max(max_prev, dp[prev_idx][d - 1] - prices[d - 1])
-            # after that try to buy with the current price
+            # after that try to sell with the current price
             dp[curr_idx][d] = max(dp[curr_idx][d - 1], max_prev + prices[d])
 
     # return the last value from the last transaction
