JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
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,
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.
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 issue


public 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<sequence.length;i++){

table[i+1]=1;
int temp =0;
for(int j=i-1;j>=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
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 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.
RSS