Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1092
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1092
Longest Increasing Sub-sequence
By Ricardo Anido Brazil
Timelimit: 1
The problem of determining the longest increasing sub-sequence in a list of numbers is already a classic in programming competitions. Despite this fact, that is the problem you must solve here. But, in order to avoid having you yawning while solving the problem, we introduced a small change: the list of numbers will be given as a bidimensional matrix, and the increasing sequence must be "embedded" in a submatrix of the original matrix.
Let's define the problem more precisely. The linearization of a bidimensional matrix is the concatenation of its lines, from the first to the last. A submatrix is a rectangular region of a bidimensional matrix (with sides paralel to the sides of the matrix). The size of a submatrix is its number of elements. You must write a program that, given a matrix of integers, determines the largest submatrix such that, when linearized, results in an increasing sequence. The figure below shows some examples of submatrices of largest size which contain increasing sequences. Notice that more than one such a submatrix may exist in a given matrix.
Input
The input contains several test cases. The first line of a test case contains two integers N and M indicating the matrix dimensions (1 ≤ N, M ≤ 600). Each one of the next N lines contains M integers, separated by a space, describing the elements of the matrix. Element Xi,j of the matrix is the j-th integer of the i-th line in the input (-106 ≤ Xi,j ≤ 106).
The end of input is indicated by a line containing only two zeros, separated by a space.
Output
For each test case in the input, your program must print one single line, containing the size of the largest sub-matrix that, when linearized, results in an increasing sequence.
Input Sample | Output Sample |
3 3 |
4 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 610;
int matriz[MAXN][MAXN], indice[MAXN][MAXN], maximocoluna[MAXN], dp[MAXN], resp,
N, M;
int main() {
while (scanf("%d %d", &N, &M) && (N || M)) {
for (int i = 1; i < = M; i++) maximocoluna[i] = 1;
for (int i = 1; i < = N; i++) {
scanf("%d", &matriz[i][1]);
indice[i][1] = 1;
for (int j = 2; j < = M; j++) {
scanf("%d", &matriz[i][j]);
if (matriz[i][j] > matriz[i][j - 1]) {
indice[i][j] = indice[i][j - 1];
maximocoluna[j] =
max(maximocoluna[j], j - indice[i][j] + 1);
} else {
indice[i][j] = j;
}
}
}
resp = 0;
for (int coluna_ini = 1; coluna_ini < = M; coluna_ini++) {
for (int coluna_fim = M; coluna_fim >= coluna_ini; coluna_fim--) {
// printf("Ci %d Cf %d\n",coluna_ini,coluna_fim);
int tam = coluna_fim - coluna_ini + 1;
if (tam > maximocoluna[coluna_fim]) continue;
if (tam * M < = resp) continue;
if (indice[1][coluna_fim] <= coluna_ini) {
dp[1] = 1;
} else {
dp[1] = 0;
}
resp = max(dp[1] * tam, resp);
for (int linha = 2; linha < = N; linha++) {
if (matriz[linha][coluna_ini] >
matriz[linha - 1][coluna_fim]) {
dp[linha] = dp[linha - 1];
} else {
dp[linha] = 0;
}
if (indice[linha][coluna_fim] < = coluna_ini) {
dp[linha]++;
} else {
dp[linha] = 0;
}
resp = max(dp[linha] * tam, resp);
}
// for(int i = 1;i < = N; i++) printf("%d ",dp[i]);
// printf("\n");
}
}
printf("%d\n", resp);
}
return 0;
}
Copy The Code &
Try With Live Editor
Input
1 2 5
4 6 7
10 8 3
3 4
1 2 1 2
9 6 7 3
8 7 2 8
4 2
-23 -12
0 2
16 15
57 33
4 4
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
0 0
Output
3
4
1