Refactor solution to the Longest Increasing Subsequence

soapyigu · soapyigu · commit 8dc4b64a6616 · 2022-10-03T14:30:39.000-07:00
diff --git a/DP/LongestIncreasingSubsequence.swift b/DP/LongestIncreasingSubsequence.swift
@@ -6,34 +6,34 @@
 
 class LongestIncreasingSubsequence {
     func lengthOfLIS(_ nums: [Int]) -> Int {
-        guard let first = nums.first else {
-            return 0
-        }
-        
-        var ends = [first]
+        var res = [nums[0]]
         
         for i in 1..<nums.count {
-            
-            // find first greater ends number
-            var left = 0, right = ends.count 
-            
-            while left < right {
-                let mid = (right - left) / 2 + left
-                
-                if ends[mid] < nums[i] {
-                    left = mid + 1
-                } else {
-                    right = mid
-                }
-            }
-            
-            if right >= ends.count {
-                ends.append(nums[i])
+            if res.last! < nums[i] {
+                res.append(nums[i])
             } else {
-                ends[right] = nums[i]
+                res[binarySearch(res, nums[i])] = nums[i]
             }
         }
         
-        return ends.count
+        return res.count
+    }
+
+    private func binarySearch(_ num: Int, _ res: [Int]) -> Int {
+        var l = 0, r = res.count - 1
+
+        while l < r {
+            let mid = (r - l) / 2 + l
+
+            if res[mid] == num {
+                return mid
+            } else if res[mid] > num {
+                r = mid
+            } else {
+                l = mid + 1
+            }
+        }
+
+        return l
     }
-}
+}
