Longest Increasing Continuous subsequence II 398

Question

Give you an integer matrix (with row size n, column size m)，find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction).

Example

Given a matrix:

[ [1 ,2 ,3 ,4 ,5],

[16,17,24,23,6],

[15,18,25,22,7],

[14,19,20,21,8],

[13,12,11,10,9] ]

return 25

Challenge

O(nm) time and memory.

Solution

这道题用记忆化搜索，因为初始状态难以确定以及转移函数复杂，用dp非常困难。

用一个和A对应的二维数组L来记录以当前元素为终点的最长连续子序列的长度，如L[i][j]表示以L[i][j]为终点的最长子序列的长度。过程如下：

1. 遍历数组每个元素，寻找以当前元素为终点的最长连续子序列的长度。

2. 对当前元素做上下左右搜索，当其四周元素比当前元素小时，则对其四周元素继续搜索。

3. 在2中，若要搜索的元素之前已经被搜索过，则直接返回结果，否则继续搜索其四周元素。这样可以避免重复搜索。

4. 可以单独再开一个二维数组来记录每个元素是否被搜索过，这样比较费空间但省时间。也可以对L的每个元素初始化为负数，若搜索过则会大于等于0，因此可以间接记录元素是否曾经被搜索过，这样需要额外初始化的时间，但是省空间。

代码如下：

public class Solution {
    /**
     * @param A an integer matrix
     * @return  an integer
     */
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    int n;
    int m;
    int[][] L;
    public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        // Write your code here
        if(A == null || A.length == 0 || A[0].length == 0){
            return 0;
        }

        int max = 0;
        n = A.length;
        m = A[0].length;
        L = new int[n][m];
        for(int i = 0; i < n; i++){
            Arrays.fill(L[i], -1);
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                L[i][j] = search(A, i, j);
                if(L[i][j] > max){
                    max = L[i][j];
                }
            }
        }

        return max;
    }

    private int search(int[][] A, int x, int y){
        if(L[x][y] >= 0){
            return L[x][y];
        }

        int res = 1;
        for(int i = 0; i < 4; i++){
            int curtX = x + dx[i];
            int curtY = y + dy[i];
            if(curtX >= 0 && curtX < n && curtY >= 0 && curtY < m && A[curtX][curtY] < A[x][y]){
                int temp = search(A, curtX, curtY) + 1;
                if(temp > res){
                    res = temp;
                }
            }
        }
        L[x][y] = res;
        return res;
    }
}