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

I know this is a very old question, but, I'm reading Lubomir Stanchev's book titled Learning Java Through Games, and the Chapter 14 Project is that exact 2D array of integers. The assignment is to find the longest increasing sequence but only in two directions, South and East, no diagonals or anything. Still it took me hours to figure out the logic, not used to the recursion either. I simplified the problem by creating auxiliary methods that check if the next index is valid in that direction (that is, not out of bounds and greater than the current value). Then I placed the base case at the start of the method, which is when there is no next possible index. The tricky part is the assignment of the String variable, so each time the method uses recursion the indexes are saved in the String. I solved it by using the String.length() method to compare the length of each sequence, when there is more than one possible path. With the basic logic in place, in order to expand the method all that it would require is creating more auxiliary methods in the direction needed, and adding those directions to the logic.

public static boolean isRightLegal(int[][] array, int row, int column) {
    //if we are at the last column
    if (column >= array[row].length - 1) {
        return false;
    }
    //if we are not at the one before last
    if ((column + 1) < array[row].length) {
        //if the current number is greater than the next
        if (array[row][column] > array[row][column + 1]) {
            return false;
        }
    }
    return true;
}

public static boolean isDownLegal(int[][] array, int row, int column) {
    //if we are at the last row
    if (row >= array.length - 1) {
        return false;
    }
    //if we are not at the one before last
    if ((row + 1) < array.length) {
        //if the current number is greater than the next
        if (array[row][column] > array[row + 1][column]) {
            return false;
        }
    }   
    return true;
}

public static String recursiveSequence(int[][] array, int row, int column, String path) {
    //base case: when we reach the end of the sequence
    if (! isDownLegal(array, row, column) && ! isRightLegal(array, row, column)) {
        return "(" + row + "," + column + ") ";
    }
    path = "(" + row + "," + column + ") ";
    //if both paths are valid
    if (isDownLegal(array, row, column) && isRightLegal(array, row, column)) {
        //calculate each sequence and pick the longest one
        if (recursiveSequence(array, (row + 1), column, path).length() > recursiveSequence(array, row, (column + 1), path).length()) {
            path += recursiveSequence(array, (row + 1), column, path);
        } else {
            path += recursiveSequence(array, row, (column + 1), path);
        }
        return path;
    }
    //if only the down path is valid
    if (isDownLegal(array, row, column)) {
        path += recursiveSequence(array, (row + 1), column, path);
    }
    //if only the right path is valid
    if (isRightLegal(array, row, column)) {
        path += recursiveSequence(array, row, (column + 1), path);
    }
    return path;
}

}

Answer 2

java complete solution It returns pathes to console, and returns longest sequence, but you can little modify this code, and you'll get longest path also

public class HedgehogProblemSolver {

private int rowCount;
private int columnCount;
private int[][] fieldArray;
private int maxApplesCount = 0;

public HedgehogProblemSolver(int inputArray[][]) {
    this.fieldArray = inputArray;
    rowCount = inputArray.length;
    columnCount = inputArray[0].length;
}

public int solveProblem() {
    findPathRecursive(0, 0, "", 0);
    System.out.println("Max apple count: " + maxApplesCount);
    return maxApplesCount;
}

private void findPathRecursive(int row, int column, String path, int applesCount) {
    if (row == rowCount - 1) {
        //last row
        for (int i = column; i < columnCount; i++) {
            //just go right until last column
            path += "-[" + fieldArray[row][i]  + "](" + row + ", " + i + ")";
            applesCount += fieldArray[row][i];
        }
        pathResult(path, applesCount);
        return;
    }
    if (column == columnCount - 1) {
        //last column
        for (int i = row; i <= rowCount - 1; i++) {
            //just go down until last row
            path += "-[" + fieldArray[i][column] + "](" + i + ", " + column + ")";
            applesCount += fieldArray[i][column];
        }
        pathResult(path, applesCount);
        return;
    }

    path = path + "-[" + fieldArray[row][column] + "](" + row + ", " + column + ")";
    applesCount += fieldArray[row][column];

    //go down
    findPathRecursive(row + 1, column, path, applesCount);
    //go right
    findPathRecursive(row, column + 1, path, applesCount);
}

private void pathResult(String path, int applesCount) {
    System.out.println("Path: " + path + "; apples: " + applesCount);
    if (applesCount > maxApplesCount) {
        maxApplesCount = applesCount;
    }
}

}

Answer 3

Another approach: Sort the matrix entries by the value in them. Iterate from the largest to the smallest. For each entry, compute the longest path in constant time: longest path is 1 + maximum over longest paths for larger neighbors (which have already been computed).

Total time: O(mn log(mn)) to sort the matrix entries, plus O(mn) to find the longest paths.

Answer 4

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