sheldon
BAN USERwe can do it by dynamic programming. here are the steps:
1. create a new 2d array (let say named temp[][]) of same dimension as original. the element temp[i][j] contains the length of the LIS starting at this point.
2. first fill this temp array with 0's.
3. now, start filling this temp array. let say given array's dimension is MxN.
int arr[M][N]; // given array.
int temp[M][N];
for (i=0;i<M;i++){
for(j=0;j<N;j++){
if(temp[i][j] == 0){
fill(temp,i,j);
}
}
}
here is fill() function.
void fill(int temp[][], int i, int j){
if(i<0 || j< 0 || i>=M || j>=N)
return 0;
if(temp[i][j] != 0)
return temp[i][j];
int left=0,right=0,up=0,down=0;
if(arr[i-1][j] = arr[i][j] +1)
up = fill(temp,i-1,j);
if(arr[i+1][j] = arr[i][j] +1)
down = fill(temp,i+1,j);
if(arr[i][j-1] = arr[i][j-1] +1)
left = fill(temp,i,j-1);
if(arr[i][j+1] = arr[i][j+1] +1)
right = fill(temp,i,j+1);
temp[i][j] = max(up,down,left,right) + 1;
return temp[i][j];
}
thus it will calculate each element of temp array only once.
4. now, find the maximum element in the array. it's value will be the length of LIS.
max_x=0,max_y=0;
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(temp[i][j] > temp[max_x][max_y]){
max_x = i;
max_y = j;
}
}
}
5. Above will give the length of LIS. now, to find the LIS, we will check it's neighbours whose LIS value difference is 1.
i=max_x, j= max_y ;
printf("%d ",temp[i][j]);
while(temp[i][j] != 1){
if(temp[i-1][j] = temp[i][j] -1){
i = i-1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i+1][j] = temp[i][j] -1){
i = i+1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j-1] = temp[i][j] -1){
j = j-1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j+1] = temp[i][j] -1){
j = j+1;
printf("%d ",temp[i][j]);
continue;
}
}
time complexity is: O(M.N)
I have edited the code to print LIS.
- sheldon August 25, 2012