 3

# Find Longest Sequence

Difficulty: MEDIUM Contributed By
Archit Sharma
Avg. time to solve
15 min
Success Rate
80%

Problem Statement
Suggest Edit

#### Only four possible movements are allowed i.e, Up, Down, Left , and Right.

##### For example :
``````Input:  Mat [ ][ ] = { { 9 , 1 , 3 }
{ 7 , 4 , 2 }
{ 6 , 5 , 8 } }
Output: 4
Explanation: The longest path is of length ‘4’ { 4 - 5 - 6 - 7 }
``````
##### Input Format :
``````The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains a single integer 'N' denoting the size of the matrix as N*N.
‘N’ lines follow. Each of the next ‘N’ lines contains ‘N’ space separated integers separated by space.
``````
##### Output Format:
``````For each test case, return an integer denoting the maximum length path.
Output for each test case should be printed in a separate line.
``````
##### Note
``````You are not required to print anything, it has already been taken care of. Just implement the function.
``````
##### Constraints :
``````1 <= T <= 100
1 <= N <= 10^3

Time Limit : 1 sec
``````
##### Sample Input 1:
``````2
3
1 2 9
5 3 8
4 6 7
4
1 15 13 14
2 8 9 10
3 11 16 12
4 5 6 7
``````
##### Sample Output 1:
``````4
7
``````
##### Explanation For Sample Output 1 :
``````In test case 1:
For ‘N’ = 3,
1 2 9
5 3 8
4 6 7
The longest path is of length ‘4’ { 6 -> 7 -> 8 -> 9 }

In test case 2:
For ‘N’ = 4,

1 15 13 14
2 8  9  10
3 11 16 12
4 5  6 7

The longest path is of length ‘7’ { 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 }
``````
##### Sample Input 2:
``````2
2
1 2
3 4
3
1 5 6
9 4 7
2 3 8
``````
##### Sample Output 2:
``````2
7
``````   Console