leetcode

commit 09d306aac02d1f24856029951da833dd8528b4f6
parent 2453d398db713270a1e644821bd365fc8d110a1c
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Thu, 25 May 2023 08:19:52 -0500

Completed best time to buy and sell stock ii using dp and memoization

Diffstat:
A
best-time-to-buy-and-sell-stock-ii/best-time-to-buy-and-sell-stock-iiV2.dart
 | 
34
++++++++++++++++++++++++++++++++++

1 file changed, 34 insertions(+), 0 deletions(-)
diff --git a/best-time-to-buy-and-sell-stock-ii/best-time-to-buy-and-sell-stock-iiV2.dart b/best-time-to-buy-and-sell-stock-ii/best-time-to-buy-and-sell-stock-iiV2.dart
@@ -0,0 +1,34 @@
+//Apparently DP and memoization are not fast enough for this problem. This is understandable
+//but kind of annoying.
+//Time: TLE
+//Memory: TLE
+class Solution {
+  int maxProfit(List<int> prices) {
+     return max(prices, 0, 0, {}); 
+  }
+  int max (List<int> prices, int owned, int val, Map<String, int> memo){
+      String mem = prices.length.toString() + " " + owned.toString();
+      if(val < (memo[mem] ?? -100000000)){
+        return -100000000;
+      }
+      else{
+        memo[mem] = val;
+      }
+      String curr_str = prices.length.toString() + " " + owned.toString();
+      if(prices.length == 0){
+          return val;
+      }
+      int buy_or_sell = 0;
+      if(owned == 1){
+        buy_or_sell = max(prices.sublist(1), 0 , val + prices[0], memo);
+      }
+      else{
+        buy_or_sell = max(prices.sublist(1), 1, val - prices[0], memo);
+      }
+      int hold = max(prices.sublist(1) , owned, val, memo);
+      if(buy_or_sell > hold){
+        return buy_or_sell;
+      }
+      return hold;
+  }
+}