JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Dynamic Programming: From novice to advanced longest non-decreasing sequence example
 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=dynProgLet'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 24 3 35 3 36 4 5I 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
 Forums Tutorial Discussions Dynamic Programming: From novice to advanced longest non-decreasing sequence example Previous Thread  |  Next Thread