leetcode

commit c7a993946c13641bd0faadce68e2156e94a92e14
parent afdb1453746fb454433383ea74f959eb4ce2f7a1
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue, 16 Dec 2025 22:16:47 -0700

3573. best time to buy and sell stock v

Diffstat:
A
best_time_buy_sell_stock5.c
 | 
62
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
best_time_buy_sell_stock5.py
 | 
38
++++++++++++++++++++++++++++++++++++++

2 files changed, 100 insertions(+), 0 deletions(-)
diff --git a/best_time_buy_sell_stock5.c b/best_time_buy_sell_stock5.c
@@ -0,0 +1,62 @@
+// 3573. Best Time to Buy and Sell Stock V
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'prices' where 'prices[i]' is the price of a
+ * stock in dollars on the i'th day, and an integer 'k'. you are allowed to make
+ * at most 'k' transactions, where each transaction can be either of the
+ * following: normal transaction is buy on day 'i', then sell on a later day 'j'
+ * where 'i < j'. short selling transaction where you sell on day 'i', then buy
+ * back on a later day 'j' where 'i < j'. note that you must complete each
+ * transaction betfore starting another. additionally, you can't buy or sell on
+ * the same day you are selling or buying back as part of a previous
+ * transaction. return the maximum total profit you can earn by making at most
+ * 'k' transactions.
+ */
+
+void swap(long long ***a, long long ***b) {
+  long long **tmp = *a;
+  *a = *b;
+  *b = tmp;
+}
+
+long long maximumProfit(int *prices, int pricesSize, int k) {
+  long long **prev = (long long **)malloc((k + 1) * sizeof(long long *));
+  long long **curr = (long long **)malloc((k + 1) * sizeof(long long *));
+  for (int i = 0; i <= k; i++) {
+    prev[i] = (long long *)malloc(3 * sizeof(long long));
+    curr[i] = (long long *)malloc(3 * sizeof(long long));
+    for (int j = 0; j < 3; j++)
+      prev[i][j] = INT_MIN;
+  }
+  for (int i = 0; i <= k; i++)
+    prev[i][0] = 0;
+  for (int i = 0; i < pricesSize; i++) {
+    for (int j = k; j >= 0; j--) {
+      curr[j][0] = prev[j][0];
+      curr[j][0] = fmax(curr[j][0], prev[j][1] + prices[i]);
+      curr[j][0] = fmax(curr[j][0], prev[j][2] - prices[i]);
+      curr[j][1] = prev[j][1];
+      curr[j][2] = prev[j][2];
+      if (j < k) {
+        curr[j][1] = fmax(prev[j][1], prev[j + 1][0] - prices[i]);
+        curr[j][2] = fmax(prev[j][2], prev[j + 1][0] + prices[i]);
+      }
+    }
+    swap(&prev, &curr);
+  }
+  long long ans = prev[0][0];
+  for (int i = 0; i <= k; i++) {
+    free(prev[i]);
+    free(curr[i]);
+  }
+  free(prev);
+  free(curr);
+  return ans;
+}
+
+int main() {
+  int p1[] = {1, 7, 9, 8, 2}, p2[] = {12, 16, 19, 19, 8, 1, 19, 13, 9};
+  printf("%lld\n", maximumProfit(p1, ARRAY_SIZE(p1), 2)); // expect: 14
+  printf("%lld\n", maximumProfit(p2, ARRAY_SIZE(p2), 3)); // expect: 36
+}
diff --git a/best_time_buy_sell_stock5.py b/best_time_buy_sell_stock5.py
@@ -0,0 +1,38 @@
+# 3573. Best Time to Buy and Sell Stock V
+
+"""
+you are given an integer array 'prices' where 'prices[i]' is the price of a
+stock in dollars on the i'th day, and an integer 'k'. you are allowed to make
+at most 'k' transactions, where each transaction can be either of the
+following: normal transaction is buy on day 'i', then sell on a later day 'j'
+where 'i < j'. short selling transaction where you sell on day 'i', then buy
+back on a later day 'j' where 'i < j'. note that you must complete each
+transaction betfore starting another. additionally, you can't buy or sell on
+the same day you are selling or buying back as part of a previous
+transaction. return the maximum total profit you can earn by making at most
+'k' transactions.
+"""
+
+
+class Solution(object):
+    def maximumProfit(self, prices, k):
+        """
+        :type prices: List[int]
+        :type k: int
+        :rtype: int
+        """
+        prev = [float("-inf")] * k
+        curr = [0] * k
+        ans = [0] * (k + 1)
+        for i in prices:
+            for j in range(k, 0, -1):
+                ans[j] = max(ans[j], prev[j - 1] + i, curr[j - 1] - i)
+                prev[j - 1] = max(prev[j - 1], ans[j - 1] - i)
+                curr[j - 1] = max(curr[j - 1], ans[j - 1] + i)
+        return max(ans)
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.maximumProfit(prices=[1, 7, 9, 8, 2], k=2))
+    print(obj.maximumProfit(prices=[12, 16, 19, 19, 8, 1, 19, 13, 9], k=3))