Geek asks and answers

Find the longest ascending subsequence in a two-dimensional array

I have this problem as homework, and I just don’t know where to start. I implemented a solution using a recursive algorithm (# 1), but I just can't figure out how to solve the problem using the stack ... any help would be great.

Find the longest ascending sequence of numbers in the 15 x 15 array. For example, if the 4x4 array contains

97  47  56  36
35  57  41  13
89  36  98  75
25  45  26  17

then the longest ascending sequence of numbers is a sequence of length eight, consisting of 17, 26, 36, 41, 47, 56, 57, 97. Note that there are no duplicates in the increasing sequence.

  • Create a recursive algorithm to solve this problem and implement it in Java.

  • Create a non-recursive algorithm to solve the same problem using the stack.

+3
source share
1 answer

Because this is homework, here's a tip: You can convert an array of numbers into a directed acyclic graph. (This is acyclic because duplicates are not allowed in the sequence). After that, you can use the algorithm to solve the longest path problem to find a simple maximum length path in your graph.

+2
source

More articles:


All Articles