leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

best-time-to-buy-and-sell-stock-iiV2.dart (1010B)

      1 //Apparently DP and memoization are not fast enough for this problem. This is understandable
      2 //but kind of annoying.
      3 //Time: TLE
      4 //Memory: TLE
      5 class Solution {
      6   int maxProfit(List<int> prices) {
      7      return max(prices, 0, 0, {}); 
      8   }
      9   int max (List<int> prices, int owned, int val, Map<String, int> memo){
     10       String mem = prices.length.toString() + " " + owned.toString();
     11       if(val < (memo[mem] ?? -100000000)){
     12         return -100000000;
     13       }
     14       else{
     15         memo[mem] = val;
     16       }
     17       String curr_str = prices.length.toString() + " " + owned.toString();
     18       if(prices.length == 0){
     19           return val;
     20       }
     21       int buy_or_sell = 0;
     22       if(owned == 1){
     23         buy_or_sell = max(prices.sublist(1), 0 , val + prices[0], memo);
     24       }
     25       else{
     26         buy_or_sell = max(prices.sublist(1), 1, val - prices[0], memo);
     27       }
     28       int hold = max(prices.sublist(1) , owned, val, memo);
     29       if(buy_or_sell > hold){
     30         return buy_or_sell;
     31       }
     32       return hold;
     33   }
     34 }