We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Super Kth LIS

Super Kth LIS

Problem
Submissions
Leaderboard
Discussions
Editorial

Given an array of integers (), find all possible increasing subsequences of maximum length, . Then print the lexicographically longest increasing subsequence as a single line of space-separated integers; if there are less than subsequences of length , print .

Two subsequences and are considered to be different if there exists at least one such that .

Input Format

The first line contains space-separated integers, and , respectively.
The second line consists of space-separated integers denoting respectively.

Constraints

Scoring

  • for of the test data.
  • for of the test data.

Output Format

Print a single line of space-separated integers denoting the lexicographically longest increasing subsequence; if there are less than subsequences of length , print .

Note: is the length of longest increasing subsequence in the array.

Sample Input 0

5 3
1 3 1 2 5

Sample Output 0

1 3 5

Sample Input 1

5 2
1 3 2 4 5

Sample Output 1

1 3 4 5    

Explanation

Sample Case 0:
The longest possible increasing subsequences in lexicographical order are:

Notice that the first and second subsequences appear the same; they are actually both different because the in the first subsequence comes from array element , and the in the second subsequence comes from array element . Because , we print the one () as a single line of space-separated integers.

Sample Case 1:
The longest possible increasing subsequences in lexicographical order are:

Because , we print the one () as a single line of space-separated integers.

Author

harshil7924

Difficulty

Advanced

Max Score

90

Submitted By

457

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature