leetcode

commit 49f87a233d43b3d2b846d179ca54d5cf8c5c93c3
parent ff794445c5856780948c6ba822df95cee9bcf46b
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Tue, 16 May 2023 13:45:02 -0500

Completed longest increasing subsequence using recursin memoization and DP.

Diffstat:
A
longest-increasing-subsequence/longest-increasing-subsequence.dart
 | 
32
++++++++++++++++++++++++++++++++

1 file changed, 32 insertions(+), 0 deletions(-)
diff --git a/longest-increasing-subsequence/longest-increasing-subsequence.dart b/longest-increasing-subsequence/longest-increasing-subsequence.dart
@@ -0,0 +1,32 @@
+//Find the longest increasing subsequence contained in a list.
+//I did this using recursion in O(n^2) time utilizing memoization to 
+//decrease required overhead.
+//Time: 4903ms Beats: 33.33%
+//Memory: 183.2MB Beats: 66.67%
+class Solution {
+    int lengthOfLIS(List<int> nums) {
+        return(lengthOfList(nums , -1000000 , 0, {}));
+    }
+
+    int lengthOfList(List<int> nums, int highest, int index, Map<String, int> memo){
+        if(nums.length == 0){
+            return 0;
+        }
+        String current_str = highest.toString() + " " + index.toString();
+        if(memo[current_str] != null){
+            int current_int = (memo[current_str] ?? 0);
+            return current_int;
+        }
+        int max = 0;
+        for(int i = index ; i < nums.length ; ++i){
+            if(nums[i] > highest){
+                int current = lengthOfList(nums, nums[i] , i , memo) + 1;
+                if(current > max){
+                    max = current;
+                }
+            }
+        }
+        memo[current_str] = max;
+        return max;
+    }
+}