Epic Systems Interview Question
Software Development ManagersCountry: United States
Interview Type: Phone Interview
your array temp[i][j] stores the length of LIS starting at that i,j . Once we have filled the whole temp[][] and u hav the element of temp[][] which is maximum.But how will u know in which direction to move from that point. We have to print the LIS and not just length of LIS
int left=0,right=0,up=0,down=0;
if(temp[i-1][j] = temp[i][j] +1)
up = fill(temp,i-1,j);
if(temp[i+1][j] = temp[i][j] +1)
down = fill(temp,i+1,j);
if(temp[i][j-1] = temp[i][j-1] +1)
left = fill(temp,i,j-1);
if(temp[i][j+1] = temp[i][j+1] +1)
right = fill(temp,i,j+1);
temp[i][j] = max(up,down,left,right) + 1;
return temp[i][j];
In this part, can we directly use temp[i-1][j] instead of up, temp[i][j-1] instead of left and so on. That could save some time complexity I think.
Please correct me if I'm wrong
This works great. But, there is a small bug in the printing stage and it should be corrected to following to get the correct answer.
while(temp[i][j] != 1){
if(i>0){
if(temp[i-1][j] == temp[i][j]-1 && arr[i-1][j]==arr[i][j]+1){
i = i-1;
System.out.println(arr[i][j]);
//System.out.println(i+" "+j);
continue;
}
}
if(i<3){
if(temp[i+1][j] == temp[i][j]-1 && arr[i+1][j]==arr[i][j]+1){
i = i+1;
System.out.println(arr[i][j]);
continue;
}
}
if(j>0){
if(temp[i][j-1] == temp[i][j]-1 && arr[i][j-1]==arr[i][j]+1){
j = j-1;
System.out.println(arr[i][j]);
continue;
}
}
if(j<3){
if(temp[i][j+1] == temp[i][j]-1 && arr[i][j+1]==arr[i][j]+1){
j = j+1;
System.out.println(arr[i][j]);
continue;
}
}
}
Why time complexity is: O(M*N)? When you compute the length of LIS for each temp[i][j], it could be at least O(1) and at most O(M*N).
What if there are more than one longest increasing path with same length, could you find all of them?
Ideas from the sheldon's, modified for holding multiple snakes exist in the same time. I think there is no bug here, just for reference.
//2,loop the matrix for filling
public int filldp(int[][] grid,int[][] dp){
if(grid.length==0 || grid[0].length==0) throw new IllegalArgumentException("");
int rows = grid.length, cols = grid[0].length;
//int[][] dp = new int[rows][cols];
int max = 0;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(dp[i][j]==0){
max = Math.max(max,fill(grid,i,j,dp));
}else{
max = Math.max(max, dp[i][j]);
}
}
}
return max;
}
//1,fill the dp matrix
public int fill(int[][] grid, int r, int c,int[][] dp){
if(r<0 || c<0 || r>grid.length-1 || c>grid[0].length-1){
return 0;
}
if(dp[r][c]!=0){
return dp[r][c];
}
int left=0,right=0,down=0,up=0;
if(r-1>=0 && grid[r-1][c]==grid[r][c]+1){
up = fill(grid,r-1,c,dp);
}
if(r+1<grid.length && grid[r+1][c] == grid[r][c]+1){
down = fill(grid,r+1,c,dp);
}
if(c-1>=0 && grid[r][c-1] == grid[r][c]+1){
left = fill(grid,r,c-1,dp);
}
if(c+1<grid.length && grid[r][c+1] == grid[r][c]+1){
right = fill(grid,r,c+1,dp);
}
dp[r][c] = Math.max(Math.max(up, down),Math.max(left, right))+1;
return dp[r][c];
}
//4, DFS for finding snake paths
public void findall(int[][] grid,int[][] dp, ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> one, int r, int c){
if(dp[r][c]==1){
one.add(grid[r][c]);
paths.add(one);
System.out.println(one);
return;
}
one.add(grid[r][c]);
if(r-1>=0 && dp[r-1][c] == dp[r][c]-1 && grid[r-1][c] == grid[r][c] +1)
findall(grid,dp,paths,new ArrayList<Integer>(one),r-1,c);
if(r+1<grid.length && dp[r+1][c] == dp[r][c]-1 && grid[r+1][c] == grid[r][c] +1)
findall(grid,dp,paths,new ArrayList<Integer>(one),r+1,c);
if(c-1>=0 && dp[r][c-1] == dp[r][c]-1 && grid[r][c-1] == grid[r][c] +1)
findall(grid,dp,paths,new ArrayList<Integer>(one),r,c-1);
if(c+1<grid[0].length && dp[r][c+1] == dp[r][c] -1 && grid[r][c+1] == grid[r][c] +1)
findall(grid,dp,paths,new ArrayList<Integer>(one),r,c+1);
}
//3,main func for finding all the snake seqs
// assume we just need to find the elements along the snake paths not the coordinates
public ArrayList<ArrayList<Integer>> findallsnakes(int[][] grid){
if(grid.length==0 || grid[0].length==0) throw new IllegalArgumentException("");
ArrayList<ArrayList<Integer>> snakes = new ArrayList<ArrayList<Integer>>();
int rows = grid.length, cols = grid[0].length;
int[][] dp = new int[rows][cols];
int max = filldp(grid,dp);
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(dp[i][j] == max){
findall(grid,dp,snakes,new ArrayList<Integer>(),i,j);
}
}
}
return snakes;
}
yes
longest increasing sub sequences
increasing means only one
Ex: 12,13,14 (correct)
12 ,15 ,38(not correct)
it means one step.
2 3 4 5
4 5 10 11
20 6 9 12
6 7 8 40
how come the output : 4 5 6 7 8 9 10 11 12
y not 2 4 5 6 7 8 9 10 11 12 40
You are also correct as a sense of increasing subsequence but here it is been asked the output should be sequential. Elements difference differ only by 1
why don't we consider the sequential string
2,3,4,5,6,7,8,9,10,11,12
Positions: (0,0) -> (0,1) -> (1,0) -> (1,1) -> (2,1) ...... etc
Here is one solution (maybe not optimal)
first it picks up smallest element in the matrix, search a longest increasing sub seq starting at this element, mark all the element on the seq using direct[][] and dist_2_end[][]
driect[i][j] means one the longest sub seq, what is the direction of next movement at i,j
dist_2_end[i][j] means the distance between i,j and the end of the longest sub seq
second, pick up the smallest element which is not marked yet, search a longest increasing sub seq starting at this elements, the search can be simplified if we search some element which is already marked. That means the rest of search should follow the longest sub seq starting at this element.
then mark the longest seq and repeat the second step while all the matrix is marked.
def findmin(a,direct):
sx=-1
sy=-1
mini=999999
for i,a1 in enumerate(a):
for j,a2 in enumerate(a1):
# print a2,
if a2<mini and direct[i][j]==-1:
sx, sy, mini = (i,j,a2)
# print
return (sx, sy)
def findlongpath(sx, sy, a, direct,dist_2_end,offset):
if direct[sx][sy]>=10:
return 0,[]
if direct[sx][sy]>=0:
return dist_2_end[sx][sy],[]
maxlen, maxdirect,maxpath= (0,-2, [])
direct[sx][sy]=10
for i,oi in enumerate(offset):
nx,ny =(sx+oi[0], sy+oi[1] )
if nx<0 or nx>=len(a) or ny<0 or ny>=len(a):
continue
# here is for the condition you want to applt yo the sequence
if a[nx][ny]!=a[sx][sy]+1:
continue
pathlen, path = findlongpath(nx,ny, a,direct, dist_2_end, offset)
if pathlen>maxlen:
maxlen=pathlen
maxpath=path[:]
maxdirect=i
direct[sx][sy]=-1
maxpath.append([sx,sy,maxdirect])
return maxlen+1, maxpath
def setpath(path,pathlen, direct, dist_2_end):
for p in path:
sx, sy, d= (p[0], p[1], p[2])
direct[sx][sy] = d
dist_2_end[sx][sy] = pathlen
pathlen-=1
a=[\
[10,10,1 ,23,-4, 5, 6,23, 7],\
[-6,10,12,3 ,-4, 5,-3,10, 7],\
[10,10,-200,23,-4,-200, 6,23,-7],\
[-2, 3,1 ,99,99, 5,32, 0,-7],\
[10, 4,7 ,8,9, 5, 6,-5,-7],\
[3 , 5,6 ,99,99,-5,-3,-5, 7],\
[18,-6,1 ,23,-4,-200, 6,4 , 7],\
[2 ,10,1 ,-2,14, 5,10,10, 7],\
[2 ,10,1 ,23,-4, 5, 2,2 , 7]\
]
N=len(a)
offset=[[1,0],[0,1],[-1,0],[0,-1]]
direct=[[-1 for j in range(N)] for i in range(N)]
dist_2_end=[[0 for j in range(N)] for i in range(N)]
sx,sy = findmin(a, direct)
lx,ly=(-1,-1)
ml,mx,my = (0,-1,-1)
while (lx!=sx or ly!=sy):
pathlen, path=findlongpath(sx,sy,a,direct,dist_2_end,offset)
path.reverse()
if ml<pathlen:
ml, mx, my=(pathlen, sx, sy)
setpath(path,pathlen, direct, dist_2_end)
lx, ly =(sx, sy)
sx,sy=findmin(a, direct)
sx, sy=(mx, my)
while ml>0:
d=direct[sx][sy]
print 'step',ml,':','[',sx, sy,']', a[sx][sy]
if d<0:
break
sx, sy = (sx +offset[d][0], sy+offset[d][1])
ml-=1
Here is the output for input
a=[\
[2, 3, 4, 5],\
[4, 5, 10, 11],\
[20, 6, 9, 12],\
[6, 7, 8, 40]
]
output:
step 9 : [ 1 0 ] 4
step 8 : [ 1 1 ] 5
step 7 : [ 2 1 ] 6
step 6 : [ 3 1 ] 7
step 5 : [ 3 2 ] 8
step 4 : [ 2 2 ] 9
step 3 : [ 1 2 ] 10
step 2 : [ 1 3 ] 11
step 1 : [ 2 3 ] 12
if the longest increasing sub seq starting at x0,y0 is {(x0,y0),(x1,y1)..,(xn,yn)}, if (xi,yi) is on the seq, then the longest sub seq starting (xi,yi) is included by the longest sub seq starting at (x0,y0)
Perhaps he means to simplify in this way. Here is a three-phase approach. In the first phase, scan the matrix to find all the elements that could be the start of a path, i.e. those elements adjacent to integer values that are "next in sequence" with respect to their own integer values, and which are not adjacent to any "previous" values. This first phase is O(N) where N = number of elements in table. In the second phase, perform an exhaustive search (depth-first perhaps) starting at each candidate beginning element, creating back-links at each step, and at each termination point record the length of that path. I think this second phase is O(N) if your search trees don't overlap, but it might be O(N^2) in the worst case. Finally, compare lengths of each termination point to find the longest, which is no worse than O(N) again.
I forgot to say how this is related to hwer.han's comment. There is no need to start searching in the middle of a sequence, because it is always included in a longer sequence.
if the longest increasing sub seq starting at x0,y0 is {(x0,y0),(x1,y1)..,(xn,yn)}, if (xi,yi) is on the seq, then the longest sub seq starting (xi,yi) is included by the longest sub seq starting at (x0,y0) -- This is not true in your case. If you take the example
a=[\
[2, 3, 4, 5],\
[4, 5, 10, 11],\
[20, 6, 9, 12],\
[6, 7, 8, 40]
]
4,5 is repeated, so if you start with 2 3 4 5 sequence, you would never pick the correct longest sequence 4 5 6 7 8 9 ... Since 4 5 already exists in the first sequence
Not Very efficient but i tried wd Dp seems not working,since we need to have information about all four values around a[i][j]..so not getting how to apply dp..
calculate(i,j,a)
{
level=0;
node b;
b->data=a[i][j];
b->level=0;
enqueue(b);
int maximum=0;
while(queue!=empty)
{
node c=dequeue;
if(c->level>maximum)
maximum=c->level;
level=level+1;
if(c->left->data=a[i][j]+1)
enqueue(c->left);
////
similary for enqueue(c->top),c->left,c->bottom)
}
return maximum;
}
int main()
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
a=calculate(i,j,a[]);
if(a>max)
max=a;
}
}
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node{
int row;
int col;
int data;
int length;
};
int main()
{
int m,n,max=0;
cin>>m>>n;
queue<node*> q;
vector<vector<int> > v(m,n);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>v[i][j];
for(int i=0;i<m;i++)
{ for(int j=0;j<n;j++)
{
node* a=new node;
a->col=j;
a->row=i;
a->data=v[i][j];
a->length=1;
q.push(a);
while(!q.empty())
{
node* b=new node;
b=q.front();
q.pop();
if(b->length>max)
max=b->length;
if(b->row+1<m)
if(v[b->row+1][b->col]==b->data+1)
{
// cout<<"down\n";
node* c=new node;
c->row=b->row+1;
c->col=b->col;
c->data=b->data+1;
c->length=b->length+1;
q.push(c);
}
if(b->row-1>=0)
if(v[b->row-1][b->col]==b->data+1)
{
//cout<<"up\n";
node* c=new node;
c->row=b->row-1;
c->col=b->col;
c->data=b->data+1;
c->length=b->length+1;
q.push(c);
}
if(b->col+1<n)
if(v[b->row][b->col+1]==b->data+1)
{
//cout<<"right\n";
node* c=new node;
c->row=b->row;
c->col=b->col+1;
c->data=b->data+1;
c->length=b->length+1;
q.push(c);
}
if(b->col-1>=0)
if(v[b->row][b->col-1]==b->data+1)
{
//cout<<"left\n";
node* c=new node;
c->row=b->row;
c->col=b->col-1;
c->data=b->data+1;
c->length=b->length+1;
q.push(c);
}
}
}
}
cout<<max;
system("pause");
return 0;
}
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node{
int row;
int col;
int data;
int length;
};
int main()
{
int m,n,max=0;
cin>>m>>n;
queue<node*> q;
vector<vector<int> > v(m,n);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>v[i][j];
for(int i=0;i<m;i++)
{ for(int j=0;j<n;j++)
{
node* a=new node;
a->col=j;
a->row=i;
a->data=v[i][j];
a->length=1;
q.push(a);
while(!q.empty())
{
node* b=new node;
b=q.front();
q.pop();
if(b->length>max)
max=b->length;
if(b->row+1<m)
if(v[b->row+1][b->col]==b->data+1)
{
// cout<<"down\n";
node* c=new node;
c->row=b->row+1;
c->col=b->col;
c->data=b->data+1;
c->length=b->length+1;
q.push(c);
}
if(b->row-1>=0)
if(v[b->row-1][b->col]==b->data+1)
{
//cout<<"up\n";
node* c=new node;
c->row=b->row-1;
c->col=b->col;
c->data=b->data+1;
c->length=b->length+1;
q.push(c);
}
if(b->col+1<n)
if(v[b->row][b->col+1]==b->data+1)
{
//cout<<"right\n";
node* c=new node;
c->row=b->row;
c->col=b->col+1;
c->data=b->data+1;
c->length=b->length+1;
q.push(c);
}
if(b->col-1>=0)
if(v[b->row][b->col-1]==b->data+1)
{
//cout<<"left\n";
node* c=new node;
c->row=b->row;
c->col=b->col-1;
c->data=b->data+1;
c->length=b->length+1;
q.push(c);
}
}
}
}
cout<<max;
system("pause");
return 0;
}
1. consider the matrix as a directed graph
2. compute the in-degree of each node
3. dynamic programming.
(1) Init a queue. If Indegree(v) == 0, put v into queue
(2) Pop a node from the queue, update the length and in-degree of its neighbour nodes
(a) length(neighbour) = max(length(node) + 1 , length(neighbour))
(b) indegree(neighbour) --;
(c) if(indegree(neighbour) == 0) put it into queue
Iterate until the queue is empty
4. return the node with max length
complexity: o(n^2)
hope this will work if not let me know thanks
int mask[100][100];
int liMaxLength,x,y;
void ClearMask()
{
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
{
mask[i][j]=0;
}
}
}
}
void PrintMask()
{
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
{
cout<<" "<<mask[i][j]<<" ";
}
}
cout<<endl;
}
cout<<"the count is "<<liMaxLength<<endl;
}
bool SnakeLength(int a[][4],int i,int j,int count)
{
bool flag=false;
count++;
if(i+1<x &&(a[i+1][j]==a[i][j]+1))
{
if(SnakeLength(a,i+1,j,count))
{
flag=true;
}
}
if(i-1 > -1 &&(a[i-1][j]==a[i][j]+1))
{
if(SnakeLength(a,i-1,j,count))
{
flag=true;
}
}
if(j+1<y &&(a[i][j+1]==a[i][j]+1))
{
if(SnakeLength(a,i,j+1,count))
{
flag=true;
}
}
if(j-1 > -1 &&(a[i][j-1]==a[i][j]+1))
{
if(SnakeLength(a,i,j-1,count))
{
flag=true;
}
}
if(liMaxLength<count)
{
ClearMask();
liMaxLength=count;
flag=true;
}
if(flag)
{
mask[i][j]=1;
return true;
}
return false;
}
int main()
{
int a[4][4]= {
2, 3, 4, 5,
4, 5, 10, 11,
20, 6, 9, 12,
6, 7, 8, 40
};
x=y=4;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(mask[i][j]!=1)
SnakeLength(a,i,j,0);
PrintMask();
cout<<endl<<endl;
}
}
PrintMask();
return 0;
}
not optimal but works; JAVA
import java.util.ArrayList;
public class snakegame {
static int array [][]= {{1,3,4,5}, {4,5,10,11}, {20, 8, 9, 12}, {6,7,8,40}};
static ArrayList <Integer> the_list = new ArrayList<Integer> ();
static ArrayList <Integer> temp_arr = new ArrayList<Integer> ();
public static void main (String []args){
for (int i = 0; i <array.length; i++){
for (int j = 0; j <array.length; j++){
add_temp(i, j);
}
}
System.out.println(the_list.toString());
}
public static void add_temp (int i, int j){
int [] indexes = get_seq(i, j);
temp_arr.add(array[i][j]);
while (indexes[0] != -1){
temp_arr.add(array[indexes[0]] [indexes[1]]);
indexes = get_seq(indexes[0], indexes[1]);
}
if (temp_arr.size() > the_list.size()){
the_list.clear();
the_list.addAll(temp_arr);
}
temp_arr.clear();
}
public static int[] get_seq (int i, int j){
int indexes[] = new int [2];
int len = array.length;
if (j+1 < len && array[i][j] == array[i][j+1]-1){
indexes[0] = i;
indexes[1] = j+1;
}
else if (j-1 >= 0 && array[i][j] == array[i][j-1]-1){
indexes[0] = i;
indexes[1] = j-1;
}
else if (i-1 >=0 &&array[i][j] == array[i-1][j]-1){
indexes[0] = i-1;
indexes[1] = j;
}
else if (i+1 < len && array[i][j] == array[i+1][j]-1){
indexes[0] = i+1;
indexes[1] = j;
}
else
indexes[0] =-1;
return indexes;
}
}
If there is something wrong, please let me know. Open to test!
import java.util.ArrayList;
import java.util.Stack;
public class LongestIncreasingSequence {
int M;
int N;
Square[][] matrix;
int[][] tab;
class Pair {
int x;
int y;
public Pair(int x, int y) {
super();
this.x = x;
this.y = y;
}
public Pair() {
// TODO Auto-generated constructor stub
}
}
class Square {
private int num;
boolean isVisited;
Square parent;
public int getNum() {
return num;
}
public Square(int num) {
super();
this.num = num;
isVisited = false;
parent = null;
}
@Override
public String toString() {
return String.valueOf(num);
}
}
public LongestIncreasingSequence(int m, int n) {
super();
M = m;
N = n;
matrix = new Square[M][N];
matrix[0][0] = new Square(2);
matrix[0][1] = new Square(3);
matrix[0][2] = new Square(4);
matrix[0][3] = new Square(5);
matrix[1][0] = new Square(4);
matrix[1][1] = new Square(5);
matrix[1][2] = new Square(10);
matrix[1][3] = new Square(11);
matrix[2][0] = new Square(20);
matrix[2][1] = new Square(6);
matrix[2][2] = new Square(9);
matrix[2][3] = new Square(12);
matrix[3][0] = new Square(6);
matrix[3][1] = new Square(7);
matrix[3][2] = new Square(8);
matrix[3][3] = new Square(40);
tab = new int[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
tab[i][j] = -1;
}
}
}
public void findLongestIncreasingSeq() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
int max = returnLargestNeighbor(i, j);
if (max != -1) {
tab[i][j] = max + 1;
} else {
int len = recursiveFind(i, j);
tab[i][j] = len;
}
}
}
}
private int recursiveFind(int i, int j) {
ArrayList<Pair> allneighbors = getSatisfiedNeighbor(i, j);
if (allneighbors.size() == 0) {
return 1;
}
int[] lens = { 0, 0, 0, 0 };
int k = 0;
for (Pair neighbor : allneighbors) {
lens[k++] = 1 + recursiveFind(neighbor.x, neighbor.y);
}
int max = Integer.MIN_VALUE;
for (int len : lens) {
if (len > max) {
max = len;
}
}
if (max == Integer.MIN_VALUE) {
matrix[i][j].parent = null;
} else if (max == lens[0]) {
// top
matrix[i][j].parent = matrix[i - 1][j];
} else if (max == lens[1]) {
// bottom
matrix[i][j].parent = matrix[i + 1][j];
} else if (max == lens[2]) {
// right
matrix[i][j].parent = matrix[i][j + 1];
} else {
// left
matrix[i][j].parent = matrix[i][j - 1];
}
return max;
}
private ArrayList<Pair> getSatisfiedNeighbor(int i, int j) {
ArrayList<Pair> pairs = new ArrayList<Pair>();
if (i - 1 >= 0
&& matrix[i - 1][j].getNum() + 1 == matrix[i][j].getNum()) {
// top
pairs.add(new Pair(i - 1, j));
}
if (i + 1 < M && matrix[i + 1][j].getNum() + 1 == matrix[i][j].getNum()) {
// bottom
pairs.add(new Pair(i + 1, j));
}
if (j + 1 < N && matrix[i][j + 1].getNum() + 1 == matrix[i][j].getNum()) {
// right
pairs.add(new Pair(i, j + 1));
}
if (j - 1 >= 0
&& matrix[i][j - 1].getNum() + 1 == matrix[i][j].getNum()) {
// left
pairs.add(new Pair(i, j - 1));
}
return pairs;
}
private int returnLargestNeighbor(int i, int j) {
int max = -1;
if (i - 1 >= 0) {
// top
if (matrix[i][j].getNum() == matrix[i - 1][j].getNum() + 1
&& tab[i - 1][j] != -1) {
if (tab[i - 1][j] > max)
max = tab[i - 1][j];
}
}
if (i + 1 < M) {
// bottom
if (matrix[i][j].getNum() == matrix[i + 1][j].getNum() + 1
&& tab[i + 1][j] != -1) {
if (tab[i + 1][j] > max)
max = tab[i + 1][j];
}
}
if (j + 1 < N) {
// right
if (matrix[i][j].getNum() == matrix[i][j + 1].getNum() + 1
&& tab[i][j + 1] != -1) {
if (tab[i][j + 1] > max)
max = tab[i][j + 1];
}
}
if (j - 1 >= 0) {
// left
if (matrix[i][j].getNum() == matrix[i][j - 1].getNum() + 1
&& tab[i][j - 1] != -1) {
if (tab[i][j - 1] > max)
max = tab[i][j - 1];
}
}
return max;
}
public void print() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
System.out.print(matrix[i][j] + "\t");
}
System.out.println();
}
}
public void printTab() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
System.out.print(tab[i][j] + "\t");
}
System.out.println();
}
}
public void output() {
System.out.println();
Stack<Square> stack = new Stack<Square>();
Pair pair = maxLength();
while (pair != null) {
stack.push(matrix[pair.x][pair.y]);
pair = nextSmallNum(pair);
}
while (!stack.isEmpty()) {
Square s = stack.pop();
System.out.print(s.getNum() + "\t");
}
System.out.println();
}
private Pair nextSmallNum(Pair pair) {
if (tab[pair.x][pair.y] == 1) {
return null;
}
Pair newpair = new Pair();
if (pair.x - 1 >= 0
&& tab[pair.x - 1][pair.y] + 1 == tab[pair.x][pair.y]) {
// top
newpair.x = pair.x - 1;
newpair.y = pair.y;
}
if (pair.x + 1 < M
&& tab[pair.x + 1][pair.y] + 1 == tab[pair.x][pair.y]) {
// bottom
newpair.x = pair.x + 1;
newpair.y = pair.y;
}
if (pair.y + 1 < N
&& tab[pair.x][pair.y + 1] + 1 == tab[pair.x][pair.y]) {
// right
newpair.x = pair.x;
newpair.y = pair.y + 1;
}
if (pair.y - 1 >= 0
&& tab[pair.x][pair.y - 1] + 1 == tab[pair.x][pair.y]) {
// left
newpair.x = pair.x;
newpair.y = pair.y - 1;
}
return newpair;
}
private Pair maxLength() {
Pair pair = new Pair();
int max = Integer.MIN_VALUE;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (tab[i][j] > max) {
max = tab[i][j];
pair.x = i;
pair.y = j;
}
}
}
return pair;
}
public static void main(String[] args) {
LongestIncreasingSequence seqMatrix = new LongestIncreasingSequence(4,
4);
seqMatrix.print();
seqMatrix.findLongestIncreasingSeq();
System.out.println();
seqMatrix.printTab();
seqMatrix.output();
}
}
#!/usr/bin/python
matrix = [[2, 3, 4, 5],[4, 5, 10, 11],[20, 6, 9, 12],[6, 7, 8, 40]]
m = len(matrix)
n = len(matrix[0])
lis = []
for i in range(m):
lis.append([0 for x in matrix[0]])
def maxd(i, j):
if lis[i][j] > 0:
return lis[i][j]
flag = False
(up, down, left, right) = (0, 0, 0, 0)
if (i < m - 1) and (matrix[i][j] == matrix[i+1][j] - 1):
down = maxd(i+1, j)
flag = True
if (j < n - 1) and (matrix[i][j] == matrix[i][j+1] - 1):
right = maxd(i, j+1)
flag = True
if (i > 0) and (matrix[i][j] == matrix[i-1][j] - 1):
up = maxd(i-1, j)
flag = True
if (j > 0) and (matrix[i][j] == matrix[i][j-1] - 1):
left = maxd(i, j-1)
flag = True
if not flag:
return 0
else:
lis[i][j] = max(up, down, left, right) + 1
return lis[i][j]
def getLIS(k, i, j):
c = str(matrix[i][j])
if k == 1:
return c
if (i < m - 1) and (lis[i][j] == lis[i+1][j] + 1):
return c + ' ' + getLIS(k-1, i+1, j)
if (j < n - 1) and (lis[i][j] == lis[i][j+1] + 1):
return c + ' ' + getLIS(k-1, i, j+1)
if (i > 0) and (lis[i][j] == lis[i-1][j] + 1):
return c + ' ' + getLIS(k-1, i-1, j)
if (j > 0) and (lis[i][j] == lis[i][j-1] + 1):
return c + ' ' + getLIS(k-1, i, j-1)
def solve(matrix):
print lis
for i in range(m):
for j in range(n):
if lis[i][j] == 0:
maxd(i, j)
print lis
(maxv, maxi, maxj) = (0, 0, 0);
for i in range(m):
for j in range(n):
if maxv < lis[i][j]:
maxv = lis[i][j]
maxi = i
maxj = j
print getLIS(maxv, maxi, maxj)
solve(matrix)
Simple recursion will do it
public class longest_subsequence
{
static ArrayList<ArrayList<Integer>> res;
static boolean[][] visited;
static int ROW, COL;
static int max;
public static void find(int[][] arr)
{
res = new ArrayList<ArrayList<Integer>>();
ROW = arr.length;
if(ROW==0) return;
COL = arr[0].length;
visited = new boolean[ROW][COL];
max = 0;
for(int row= 0;row<ROW;row++)
for(int col=0;col<COL;col++)
if(!visited[row][col])
DFS(arr,row,col,new ArrayList<Integer>());
for(ArrayList<Integer> ls: res)
System.out.println(ls);
}
public static void DFS(int[][] arr, int row, int col, ArrayList<Integer> ans)
{
visited[row][col]=true;
ans.add(arr[row][col]);
if(ans.size()>= max)
{
if(ans.size()>max) res.clear();
res.add(new ArrayList<Integer> (ans));
max = ans.size();
}
int cur = arr[row][col];
if(row>0 && cur-arr[row-1][col] ==-1 )
DFS(arr,row-1,col,ans);
if(col>0 && cur-arr[row][col-1] ==-1 )
DFS(arr,row,col-1,ans);
if(row<ROW-1 && cur-arr[row+1][col] ==-1)
DFS(arr,row+1,col,ans);
if(col<COL-1 && cur-arr[row][col+1] ==-1 )
DFS(arr,row,col+1,ans);
ans.remove(ans.size()-1);
}
public static void main(String[] args)
{
int[][] arr = {
{2,3,4,5},
{4,5,10,11},
{20,6,9,12},
{6,7,8,40}
};
find(arr);
}
}
public static int findGridLIS(int A[][]){
int len = A.length;
int dp [][] = new int [len][len];
int max =0;
//intialize memoizing array with all ones
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
int tempmax = fillDP(A,dp,i,j)+1;
if(tempmax > max)
max = tempmax;
}
}
return max;
}
public static int fillDP(int [][]A,int[][]dp,int i,int j){
int len = A.length;
if(i <0 || j < 0 || i >= len || j >= len ){
return 0;
}
if(dp[i][j] != 0)
return dp[i][j];
int left=0,right=0,topLeft=0,topRight=0,bottom=0,top=0,bottomLeft=0,bottomRight=0;
if(j-1 >= 0&& A[i][j] < A[i][j-1])
left = fillDP(A,dp,i,j-1);
if(j+1<len && A[i][j] < A[i][j+1])
right = fillDP(A,dp,i,j+1);
if(i+1 <len && A[i][j] < A[i+1][j])
bottom = fillDP(A,dp,i+1,j);
if(i-1 >=0 && A[i][j] < A[i-1][j])
top = fillDP(A,dp,i-1,j);
if(i+1 < len && j-1 >=0 && A[i][j] < A[i+1][j-1])
bottomLeft = fillDP(A,dp,i+1,j-1);
if(i+1 >len && j+1 >len && A[i][j] < A[i+1][j+1])
bottomRight = fillDP(A,dp,i+1,j+1);
if(i-1 >=0 && j-1 >=0 && A[i][j] < A[i-1][j-1])
topLeft = fillDP(A,dp,i-1,j-1);
if(i-1 >=0 && j+1 <len && A[i][j] < A[i-1][j+1])
topRight = fillDP(A,dp,i-1,j+1);
dp[i][j]= Math.max(Math.max(Math.max(top,bottom),Math.max(right,left)),Math.max(Math.max(bottomRight,bottomLeft),Math.max(topLeft,topRight))) +1;
return dp[i][j];
}
POJ1088
poj.org/problem?id=1088
(chinese). DFS with memoization.
int helper(int row, int col, vector<vector<int>> &grid, vector<vector<int>> &memo) {
if (memo[row][col] != 0) return memo[row][col];
// at least one step is possible, since the sequence can be
// only one element.
int up(0), down(0), left(0), right(0);
if (row > 0 && grid[row - 1][col] == grid[row][col] + 1)
up = helper(row - 1, col, grid, memo);
if (row < grid.size() - 1 && grid[row + 1][col] == grid[row][col] + 1)
down = helper(row + 1, col, grid, memo);
if (col > 0 && grid[row][col - 1] == grid[row][col] + 1)
left = helper(row, col - 1, grid, memo);
if (col < grid[0].size() - 1 && grid[row][col + 1] == grid[row][col] + 1)
right = helper(row, col + 1, grid, memo);
memo[row][col] = max(max(up, down), max(left, right)) + 1;
return memo[row][col];
}
The above code will only output the length of longest LIS from current coordinate. To get the full sequence, check full code at:
ideone.com/s4ILPd
we can do it by dynamic programming. here are the steps:
- sheldon August 24, 20121. 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)