Longest Increasing Subsequence (Binary Search)
DP on LIS DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Optimized Longest Increasing Subsequence (LIS) using Binary Search, Arrays, Subsequences, Dynamic Programming, Binary Search, Optimization, Time Complexity, Space Complexity, Algorithm, complexity analysis, dynamic programming, greedy algorithm, array manipulation, binary search, Lower & Upper Bound.
Problem Statement You are given an array of integers. Your task is to find the length of the longest increasing subsequence (LIS). A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. An increasing subsequence is a subsequence where each element is strictly greater than the preceding element. Input Specification The first line contains a single integer N (1 <= N <= 2 10^5), representing the number of elements in the array. The second line contains N space separated integers A[1], A[2], ..., A[N] ( 10^9 <= A[i] <= 10^9), representing the elements of the array. Output Specification Print a single integer, the length of the longest increasing subsequence. Sample Test Case Input: 8 10 9 2 5 3 7 101 18 Output: 4 Explanation of Sample Output: For the given input array [10, 9, 2, 5, 3, 7, 101, 18], some of the increasing subsequences are: [2, 5, 7, 101] (length 4) [2, 3, 7, 101] (length 4) [2, 5, 7, 18] (length 4) The longest increasing subsequence has a length of 4.