# [Community Puzzle] Longest Increasing Subsequence

Coding Games and Programming Challenges to Code Better

Created by @YuToutCourt,validated by @Timinator,@coolman14321 and @Tee-Resa.
If you have any issues, feel free to ping them.

Looks like a typo in the â€śConstraintsâ€ť section. Is specified: â€ś2 <= N <= 100â€ť. In this case, the tests contain many more lines.

1 Like

Thank you for pointing it out. Someone forgot to update the constraint after cases were added. Iâ€™ve left a comment in the contribution view to request for its update.

Hi, can someone give me some hints for this puzzle?

This is my current approach: I create multiple tables with each one containing the sequence of increasing numbers, checks if i can add the number scanned with scanf in the table, and eventually look which of the table has the highest number at the end.

• If the number scanned with scanf is bigger than the latest entry, I add the entry to each table
• If itâ€™s equal I ignore it
• If itâ€™s lower than the last number of the table but bigger than the second to last I replace the last entry of the table
• If itâ€™s lower than the last number of the table but and equal to the second to last, I ignore it
• In the last case I create a new table with the number scanned with scanf and all the previous lower numbers.

Would this be the current approach?
I am not sure how to handle the last case, my intuition would be to use recursion, but I feel like I am missing something

Can you tell me more? Which test cases are you passing and which are you failing? It sounds like maybe youâ€™re passing all the test cases except the last one, is that true?

This is a wonderfully traditional dynamic programming problem. I think you will want some efficient looping, but I donâ€™t think recursion will be critical.

Can someone give me a hint ? I get a timeout on the last test case.
I create a table with the sequence then loop through it and for each one try to find the longest subsequence. I stock the results (longest subsequence for each) in a separate table, so for each number, if I havenâ€™t caluculate yet, I test every number remaining (and again for each of them I check if I didnâ€™t calculate it)

I donâ€™t see how I can optimize further to pass the last test case

[mod edit: avoid posting code on the forum]

I guess the issue is that you have done a lot of recursions but you do not store any intermediate results for later use, resulting in repeating recursions.