Elder in Residence Soup\'s On :30pm to 10.30pm Club Dav 2. Maximum Increasing Su

Question

Elder in Residence Soup's On :30pm to 10.30pm Club Dav 2. Maximum Increasing Subsequence USINGT JAVA Find the longest increasing sequence in a two-dimensional grid of numbers. A sequence is simply a series of adjacent squares. Squares may not be used twice. Example: in the following grid: 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 The longest increasing sequence has length 10, consisting of entries (,c) (row and column, starting at zero) as follows: (5,0) with cost 12 (6,0) with cost 14 (6,1) with cost 15 (6,2) with cost 20 (7,2) with cost 44 (7,3) with cost 52 (7,4) with cost 54 (6,3) with cost 71 (5,3) with cost 74 (4,3) with cost 96 Note that the 96 adjacent to the 96 in the answer reported above could be substituted in the maximum increasing sequence, but both cannot be in the sequence, because the sequence must be strictly increasing. The Input: The input file consists of the grid of numbers. You'll need to figure out the size of the grid. Read the file into an List of Strings; the size of the List is the number of rows. Then use a StringTokenizer. Strategy You'll need to use recursion. Although a non-recursive solution is possible, I want a clean recursive backtracking algorithm;

Explanation / Answer

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

public class ProblemSolver {

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

public ProblemSolver(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;
}

//second method

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

}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.