JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
longest non-decreasing sequence example | Reply
The longest non-decreasing sequence example discussed in this tutorial
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
ends with a table which has 3 columns. The last column being the "The last sequence i from which we "arrived" to this one". In the last row the table when i = 6, this column has value 4 which means that we have arrived at this from the sequence when i was 4, which is when the sequence was 3,4,8. I might be wrong but in my opinion, but we have arrived at the last entry (column 3 and i = 6) from when i = 5 ie. when we had two longest non-decreasing sequences 3,4,8 and 3,4,6. Shud the entry in this spot not be 5, instead of 4. Pls correct me if I am wrong.
Re: longest non-decreasing sequence example (response to post by rohitabcd) | Reply
I think you're right
Re: longest non-decreasing sequence example (response to post by rohitabcd) | Reply
That's right, the table has the wrong value for the last entry, it should be 5, not 4, and that makes the elementary example quite confusing for DP beginners...
Re: longest non-decreasing sequence example (response to post by lonedfx) | Reply
So is anyone fixing this ?
Re: longest non-decreasing sequence example (response to post by thor_hayek) | Reply
The procedure for fixing something is to send an email to service@topcoder.com or follow the instructions in the bugs forum. No one that fixes stuff is going to see anything posted here.
Re: longest non-decreasing sequence example (response to post by rohitabcd) | Reply
Hi Rohit,

link to tutorial: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
Let's see what happens for a randomly generated sequence: 5, 3, 4, 8, 6, 7:

1 1 1 (first number itself)
2 1 2 (second number itself)
3 2 2
4 3 3
5 3 3
6 4 5

I think that the second column is correct(3,4,6,7) but the last entry seems to be wrong according to my understanding. shouldn't it be 3? Could you please help me understand?
Re: longest non-decreasing sequence example (response to post by ol0rin) | Reply
Hello.

Actually, I also cannot really understand how the value can become 5.
Besides what was mentioned above by ol0rin, tutorial also says to increase by one: "we make S[i]=S[j]+1"
Please, anyone clarify more why it is 5.
Thanks.
Re: longest non-decreasing sequence example (response to post by rohitabcd) | Reply
Hey,

I am not sure I exactly understand the problem.
Does the sequence has to be consecutive?
Or the goal is to find the maximum number of numbers appearing after each other in a non-decreasing manner with or without any other number between them?

Thanks
RSS