Longest Increasing Subsequence
DP on LIS DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Longest Increasing Subsequence (LIS) - Definition, Concept of Subsequences, and Dynamic Programming Approaches, Subsequences, Dynamic Programming, Recursion, Memoization, Time Complexity, Space Complexity, Arrays, Brute Force, Overlapping Subproblems, Optimal Substructure, Base Cases, complexity analysis, dynamic programming, brute force, memoization, recursion, Longest Increasing Subsequence (LIS).
Longest Increasing Subsequence Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7]. Input Specification The first line contains a single integer n (1 <= n <= 2500), the number of elements in the array. The second line contains n integers nums[0], nums[1], ..., nums[n 1] ( 10^9 <= nums[i] <= 10^9). Output Specification Return a single integer, the length of the longest increasing subsequence. Sample Test Cases Sample Input 1: Sample Output 1: Explanation: The longest increasing subsequence is [2, 3, 7, 18] or [2, 5, 7, 18], which has a length of 4. Difficulty: Medium