[Community Puzzle] Longest Increasing Subsequence

Puzzles
#1

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.

#2

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

1 Like
#3

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.

#4

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

#5

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.

#6

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 :frowning:

[mod edit: avoid posting code on the forum]

#7

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.