If data structure augmentation and designing algorithms give you a high and you wish to post in this forum email me(Inder) at inder.pall@gmail.com
DISCLAIMER : questions posted here could be from multiple source, i'll try my best to provide credit.
Here x is first element and y is successive of x. Call this method as lcs(1,2,1); x,y are first,second element of array. len is initial length which is 1.
void lcs(int x, int y, int len) { if( y <= array.length-1){ if( array[x] <= array[y]){ if( largest < len +1){ largest = len+1; } lcs(y,y+1,len+1); }else{ lcs(x-1,y,len -1); lcs(x,y+1,len); }
5 comments:
Here x is first element and y is successive of x. Call this method as lcs(1,2,1); x,y are first,second element of array. len is initial length which is 1.
void lcs(int x, int y, int len) {
if( y <= array.length-1){
if( array[x] <= array[y]){
if( largest < len +1){
largest = len+1;
}
lcs(y,y+1,len+1);
}else{
lcs(x-1,y,len -1);
lcs(x,y+1,len);
}
}
}
Recursive equation;
f(x,y) = {
x <= y , f(y,y+1,len+1)
x > y , f(x-1,y,len-1), f(x,y+1,len)
}
Use dynamic programing O(n) solution
can u please write the code or give some link or @LEAST xplain ur logic of 0(n)
O(n) is impossible.
O(n log n) :
http://en.wikipedia.org/wiki/Patience_sorting
Post a Comment