Print Longest Increasing Subsequence

Dynamic Programming LIS Easy

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.

Examples:

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, 50, 60, 80] and it is the lexicographically smallest.

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.

Input: arr = [5, 6, 1, 2, 3, 4, 7]

Constraints

  • 1 <= arr.length <= 103
  • -106 <= arr[i] <= 106

Hints

  • "Define dp[i] as the length of the LIS ending at arr[i]. Define parent[i] to track the previous element in the LIS path. Find the maximum LIS length. Backtrack using parent[i] to reconstruct the sequence. "
  • "Instead of using dp[i], maintain a sorted array (sub) where: Each element in sub represents the smallest ending element of an increasing subsequence of a certain length. Use Binary Search (lower_bound) to find the position where arr[i] should replace an element in sub."