Longest Increasing Sequence 2D matrix recursion

Question

I have been presented with a new homework assignment that has been somewhat frustrating to say the least. Basically, I have a create a 2D array of integers as follows:

97 47 56 36 60 31 57 54 12 55 
35 57 41 13 82 80 71 93 31 62 
89 36 98 75 91 46 95 53 37 99 
25 45 26 17 15 82 80 73 96 17 
75 22 63 96 96 36 64 31 99 86 
12 80 42 74 54 14 93 17 14 55 
14 15 20 71 34 50 22 60 32 41 
90 69 44 52 54 73 20 12 55 52 
39 33 25 31 76 45 44 84 90 52 
94 35 55 24 41 63 87 93 79 24

and I am to write a recursive method, or function as you will, to calculate the longest increasing sub sequence. In this example, the longest increasing sub sequence is the following:

(5,0)   with value 12
(6,0)   with value 14
(6,1)   with value 15
(6,2)   with value 20
(7,2)   with value 44
(7,3)   with value 52
(7,4)   with value 54
(6,3)   with value 71
(5,3)   with value 74
(4,3)   with value 96

So, not only am I to check N,S,E,W for values strictly greater, but I also have to account for diagonals. I have done extensive research in how to solve this recursively however I haven't had much luck, and recursion is my weakest subject (yes I know how powerful it can be in certain situations). I have seen something similar posted, where someone mentioned an acrylic graph, but that's not what I am looking for.

So far, I've basically padded my 2D array with 0's so that I don't have to worry about bounding, and I am using nested for loops to traverse the 2D array. Within those loops I am basically checking if N,NE,E,SE,S,SW,W,NW have a greater value than the current element. Sorry if I upset some of you this is my first attempt at a post. If you need me to post some code, I will do so. Thank you very much for your time!

Answer 1

Update

I learnt dynamic programming recently, and I have found a better algorithm for the question.

The algorithm is simple: find the longest length for every point, and record the result in a 2D array so that we do not need to calculate the longest length for some points again.

int original[m][n] = {...};
int longest[m][n] = {0};

int find() {
    int max = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int current = findfor(i, j);
            if (current > max) { max = current; }
        }
    }
    return max;
}

int findfor(int i, int j) {
    if (longest[i][j] == 0) {
        int max = 0;
        for (int k = -1; k <= 1; k++) {
            for (int l = -1; l <= 1; l++) {
                if (!(k == 0 && l == 0) &&
                    i + k >= 0 && i + k < m &&
                    j + l >= 0 && j + l < n &&
                    original[i + k][j + l] > original[i][j]
                   )
                    int current = findfor(i + k, j + l);
                    if (current > max) { max = current; }
                }
            }
        }
        longest[i][j] = max + 1;
    }
    return longest[i][j];
}    

---

Recursion

1) start with a point (and this step has to be taken for all necessary points)

2) if no surrounding point is greater, then this path ends; else pick a greater surrounding point to continue the path, and go to 2).

2.1) if the (ended) path is longer than recorded longest path, substitute itself as the longest.

---

Hint

(less computation but more coding)

For the longest path, the start point of which will be a local minimum point, and the end point of which will be a local maximum point.

Local minimum, less than (or equal to) all (at most) 8 surrounding points.

Local maximum, greater than (or equal to) all (at most) 8 surrounding points.

Proof

If the path does not start with a local minimum, then the start point must be greater than at least a surrounding point, and thus the path can be extended. Reject! Thus, the path must start with a local minimum. Similar for the reason to end with a local maximum.

---

pseudo code

for all local minimum
  do a recursive_search

recursive_search (point)
  if point is local maximum
    end, and compare (and substitute if necessary) longest
  else
    for all greater surrounding points
      do a recursive_search