Longest Increasing Sub-sequence

The Problem

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.

The 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 of the next N lines contains M integers, separated by a space, describing the elements of the matrix. Element X_i,j of the matrix is the j-th integer of the i-th line in the input (-10⁶ ≤ X_i,j ≤ 10⁶).

The end of input is indicated by a line containing only two zeros, separated by a space.

The 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.

Sample Input

3 3
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

Sample Output

4
3
4
1

---

題目描述：

找一個嚴格遞增的子矩陣，嚴格遞增的方式依序讀每一行，所造成得的遞增。

而不是矩陣內每個元素嚴格大於左方和上方。

題目解法：

一開始誤會題目了，總之以下做法在 O(n^3) 完成。
任舉兩列，然後用 greedy 的方式由上方掃描到下方，
中間使用 DP 的方式去計算這兩列之間的元素是否遞增。

如果能加入跳躍表應該能更加地快速。 

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int n, m, g[605][605];
int main() {
    int i, j, k;
    while(scanf("%d %d", &n, &m) == 2) {
        if(n+m == 0)
            break;
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                scanf("%d", &g[i][j]);
        int ret = 0;
        for(i = 0; i < m; i++) {
            int sum[605] = {};
            for(j = i; j < m; j++) {
                int height = j - i + 1;
                int l = 0, r = 0;
                for(k = 0; k < n; k++) {
                    if(height == 1)
                        sum[k] = 1;
                    else {
                        if(g[k][j] > g[k][j-1])
                            sum[k]++;
                    }
                    r = k;
                    if(r-1 >= l && g[r-1][j] >= g[r][i])
                        l = max(l, k);
                    if(sum[k] != height) l = max(l, k+1);
                    ret = max(ret, (r-l+1)*height);
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}