CODEWITHSUNDEEP
javaalgorithm
Vasu
Vasu

Reputation: 159

Finding maximum length of a path in an 2D array with given condition

Hi I am new to stack overflow. I need help to solve the below issue in a java program

I have a 2D array, i need to find out the maximum length that can traverse from any node. I can traverse from one element to connected element (left/right/top/bottom) if that has lesser value than current element. i need to find the maximum path that can be possible with the above condition in a 2D integer array below is 5*5 array

  7  2  3  4  5 
  36 37 38 34 6 
  33 44 46 40 7 
  24 43 42 41 8 
  35 32 47 30 9

Longest path in the above array is 46-44-43-42-41-30-9-8-7-6-5-4-3-2 total 14.

please help me on this writing Java code.Thanks in advance

Upvotes: 1

Views: 1570

Answers (1)

amit
amit

Reputation: 178451

Represent the data as a graph, where G=(V,E) and V={ all squares}, E = { (u,v) | u is adjacent to v and u.value < v.value)

Note that the above graph is a Directed Acyclic Graph (since if (u,v) is in E, there is no path from v to u, because it will require a path v->v1->v2->...->u such that v.value > v1.value > v2.value > .... > u.value, but operator> is transitive so it means v.value > u.value, and we know v.value < u.value - because (u,v) is in E, so it is a contradiction, and such a path cannot exist).

After this reduction - you can simply solve longest path in a DAG, which is a simpler problem.

Upvotes: 1

Related Questions