Longest Increasing Subsequence Length
Attention: This post was updated to include the alternate solution that uses binary search. It reduces the Time Complexity from O(n * n) to O(n * log n). Before we present the question. Let’s figure out what a subsequence is: What’s a subsequence? Any selection of items from the original array. The selection must respect the order. Meaning for [1,2,3,4,5] only two of the four below are subsequences: [1,2,3,4,5] ✅ [1,4,3,2,5] ❌ order not respected [1,2,5] ✅ [5,1] ❌ order not respected What’s the difference between a subsequence and a subarray?...