Longest increasing subsequence

Question

Longest increasing subsequence Given an array arr, write a function to find the length of the longest increasing subsequence. Example 1 > - **Input:** arr = [9, 5, 10, 6, 9, 7, 8] > - **Output:** 4 > - **Explanation:** [5, 6, 7, 8] is the longest increasing subsequence. Example 2 > - **Input:** arr = [5, 6, 1, 4, 3, 8, 2] > - **Output:** 3 > - **Explanation:** [5, 6, 8] is the longest increasing subsequence. Example 3 > - **Input:** arr = [9, 5, 4, 3] > - **Output:** 1 > - **Explanation:** [9], [5], [4] and [3] are all the longest increasing subsequences.

Accepted Answer

Optimal Solution: Time Complexity O(N), Space Complexity O(1). Codeintuition provides an interactive coding environment for this problem.