Find the longest increasing subsequence in a 2-D array

Question

I have this problem as homework and I really just have no idea where to begin. I have implemented the solution using a recursive algorithm (#1), but I just cannot figure out how to solve the problem using a stack... any assistance would be great.

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

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

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

1. Design a recursive algorithm to solve this problem and implement it in Java.

2. Design a non-recursive algorithm to solve the same problem using a stack.

Answer 1

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