1059. Print Longest Increasing Subsequence
Given an array of n integers arr, return the Longest Increasing Subsequence (LIS) that is Index-wise Lexicographically Smallest.
The Longest Increasing Subsequence (LIS) is the longest subsequence where all elements are in strictly increasing order.
A subsequence A1 is Index-wise Lexicographically Smaller than another subsequence A2 if, at the first position where A1 and A2 differ, the element in A1 appears earlier in the array arr than corresponding element in S2.
Your task is to return the LIS that is Index-wise Lexicographically Smallest from the given array.
Example 1:
Input: arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
Output: [10, 22, 33, 50, 60, 80]
Explanation: The LIS is [10, 22, 33, 41, 60, 80] and it is the index-wise lexicographically smallest.
Example 2:
Input: arr = [1, 3, 2, 4, 6, 5]
Output: [1, 3, 4, 6]
Explanation: Possible LIS sequences are [1, 3, 4, 6] and [1, 2, 4, 6]. Since [1, 3, 4, 6] is Index-wise Lexicographically Smaller, it is the result.
Now Your Turn!
Pick the correct output for the given inputInput: arr = [5, 6, 1, 2, 3, 4, 7]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= arr.length <= 103
- -106 <= arr[i] <= 106