leetcode

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

longest-increasing-subsequence.dart (1054B)

      1 //Find the longest increasing subsequence contained in a list.
      2 //I did this using recursion in O(n^2) time utilizing memoization to 
      3 //decrease required overhead.
      4 //Time: 4903ms Beats: 33.33%
      5 //Memory: 183.2MB Beats: 66.67%
      6 class Solution {
      7     int lengthOfLIS(List<int> nums) {
      8         return(lengthOfList(nums , -1000000 , 0, {}));
      9     }
     10 
     11     int lengthOfList(List<int> nums, int highest, int index, Map<String, int> memo){
     12         if(nums.length == 0){
     13             return 0;
     14         }
     15         String current_str = highest.toString() + " " + index.toString();
     16         if(memo[current_str] != null){
     17             int current_int = (memo[current_str] ?? 0);
     18             return current_int;
     19         }
     20         int max = 0;
     21         for(int i = index ; i < nums.length ; ++i){
     22             if(nums[i] > highest){
     23                 int current = lengthOfList(nums, nums[i] , i , memo) + 1;
     24                 if(current > max){
     25                     max = current;
     26                 }
     27             }
     28         }
     29         memo[current_str] = max;
     30         return max;
     31     }
     32 }