Printing Longest Increasing Subsequence
DP on LIS DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Tabulation and Dynamic Programming Approaches for Longest Increasing Subsequence (LIS), Dynamic Programming, Tabulation, Space Optimization, Subsequences, Time Complexity, Space Complexity, Arrays, Loops, Optimization, Optimal Substructure, Overlapping Subproblems, Base Cases, memoization, space optimization, tabulation, dynamic programming, Longest Increasing Subsequence (LIS).
Longest Increasing Subsequence Given an integer array nums, return the length of the longest strictly increasing subsequence. Additionally, print one such longest 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 an integer N, the size of the array. The second line contains N space separated integers nums[i]. Output Specification: First line: An integer representing the length of the longest strictly increasing subsequence. Second line: Space separated integers representing one such longest increasing subsequence. Constraints: 1 <= N <= 2500 10^4 <= nums[i] <= 10^4 Sample Test Cases: Input: Output: