[Community Puzzle] Longest Increasing Subsequence

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

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.