Problem 1 Find the longest increasing sequence of Problem 1

Problem 1. Find the longest increasing sequence of... Problem 1. 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 a program in Java to solve the same problem using a stack and run your program with given test data file. 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. Design and write a program in Java to solve the same problem using a stack and run your program with given test data file. Run your programs for an input data. NOTE: A 15 x 15 matrix is generated by a random function. Output: Print the complete longest increasing sequence of numbers with their positions. (It is an sample output for the 4x4 example above.) 17 (3,3) 26 (3,2) 36 (2,1) 41 (1,2) 47 (0,1) 56 (0,2) 57 (1,1) 97 (0,0) The length of the sequence is 8.

Solution

int original[m][n] = {...}; // let m and n be 15
int longest[m][n] = {0};

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

int arr(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 = arr(i + k, j + l);
if (current > max) { max = current; }
}
}
}
longest[i][j] = max + 1;
}
return longest[i][j];
}