Längste Steigende Sequenz 2D-matrix-Rekursion

Update

Lernte ich die dynamische Programmierung vor kurzem, und ich gefunden haben, einen besseren Algorithmus für die Frage.

Der Algorithmus ist einfach: finden Sie die längste Länge für jeden Punkt, und zeichnen Sie das Ergebnis in ein 2D-array, so dass wir nicht brauchen, zu berechnen, der längsten Länge, die für einige Punkte wieder.

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];
}    

Rekursion

1) beginnen Sie mit einem Punkt (und dieser Schritt muss für alle erforderlichen Punkte)

2) wenn Nein umliegenden Punkt größer ist, dann ist dieser Weg endet; sonst wählen Sie eine größere umliegende Punkt, um weiter den Weg, und gehe zu 2).

2.1), wenn die (Ende) - Pfad ist länger als aufgenommen längsten Pfad, ersetzen, selbst als die längste.

Hinweis

(weniger Berechnung, aber mehr Code)

Für den längsten Pfad, der start-Punkt ein lokales minimum, und der Endpunkt wird ein lokales maximum zeigen.

Lokales minimum, kleiner als (oder gleich) alle (am meisten) 8 umliegende Punkte.

Lokales maximum, größer als (oder gleich) alle (am meisten) 8 umliegende Punkte.

Nachweis

Wenn der Pfad nicht mit einem lokalen minimum, dann der start-Punkt muss größer sein als mindestens einer umlaufenden Punkt, und damit ist der Weg verlängert werden kann. Ablehnen! Also, der Pfad muss beginnen mit einem lokalen minimum. Ähnlich aus dem Grund, um am Ende mit einem lokalen maximum.

pseudo-code

für alle lokalen minimum 
tun recursive_search 

recursive_search (Punkt) 
wenn der Punkt ist lokales maximum 
Ende, und vergleichen (und ersetzen, wenn notwendig) längste 
sonst 
für alle größeren umliegenden Punkte 
tun recursive_search 

InformationsquelleAutor der Antwort Dante is not a Geek

java-Komplettlösung
Es gibt Pfade in die Konsole und kehrt längste Sequenz, aber Sie können etwas ändern diesen code, und Sie bekommen die längste Pfad auch

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;
    }
}

}

InformationsquelleAutor der Antwort Eugene Kisly