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 (oldest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Dynamic Programming: From novice to advanced Find the length of the longest non-decreasing sequence
 Re: Find the length of the longest non-decreasing sequence (response to post by blizzard_one) | Reply This seems incorrect to me as well. For the given sequence [5, 3, 4, 8, 6, 7] the longest non-decreasing sequence I see is [3, 4, 8]. I don't understand how he got a sequence length of 4 as the last table entry, unless this is a specific bug of incrementing the longest non-decreasing sequence length when the algorithm saw the [6,7] elements and missed resetting the length to 1 on encountering the 6 element.
 Re: Find the length of the longest non-decreasing sequence (response to post by hans1025) | Reply I could not understand the longest non-decreasing subsequence table. What is the sequence supposed to be and for the given example?
 Re: Find the length of the longest non-decreasing sequence (response to post by hans1025) | Reply My attempt: Java code. Pease let me know in case you find any bug or issuepublic class LongestSequence { //int[] sequence = {5,3,4,8,6,7,5,6,10,9,11}; int[] sequence = {4,3,5,2,1,3,2,3}; int[] table = new int[sequence.length+1]; public static void main(String[] args) { LongestSequence ls = new LongestSequence(); ls.getLongestSequence(); } private void getLongestSequence() { table[1] =1; for(int i=1;i=0;j--){ if(sequence[i]>sequence[j]){ if(temp==0){ temp = sequence[j]; } if(sequence[j]<=temp){ table[i+1] = 1 + table[i+1]; temp = sequence[j]; } }else{ continue; } } if(table[i+1]>table[i]){ }else{ table[i+1]=table[i]; } } } }
 Re: Find the length of the longest non-decreasing sequence (response to post by hans1025) | Reply (a1, a2,.., an)F[i] is the length of the longest non-decreasing.Algorithm:F[i] = 1, i:1..n;F[i] = max(F[j]+1, a[i]>=a[j], i:1..n, j:1..i-1);=> O(n^2)Input: 4,3,5,2,1,3,2,3=> Output: max(F[i], i:1..n) => 3.
 Find the length of the longest non-decreasing sequence | Reply The algorithm about finding the length of the longest non-decreasing sequence seems not working with the sequence: 4,3,5,2,1,3,2,3. The longest length should be 3, however the algorithm gives 4. Am missing something here?Thanks,
 Forums Tutorial Discussions Dynamic Programming: From novice to advanced Find the length of the longest non-decreasing sequence Previous Thread  |  Next Thread