Lintcode 398. Longest Continuous Increasing Subsequence II

398. Longest Continuous Increasing Subsequence II

中文English

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.

Analysis:
The naive solution would be just doing DFS. Starting from each point A(i, j), find out the longest increasing subsequence. It's however, very inefficient. For e.g. 
2 3 4 5, starting from 2 the len is 4. If there is another 1 we see later, 

1
2 3 4 5
we will re-calculate the 2 3 4 5 again. We need to memorize the longest subsequence from each point A[i][j]. If next time we saw it's not 0, means we have already calculated the point. So we can just return.

Code (Java):

public class Solution {
    /**
     * @param matrix: A 2D-array of integers
     * @return: an integer
     */
    public int longestContinuousIncreasingSubsequence2(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        // memo[i][j] means the lcs starting from memo[i][j]
        //
        int[][] memo = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                memo[i][j] = 0; // 
            }
        }

        int maxLen = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxLen = Math.max(maxLen, lcsHelper(i, j, matrix, memo));
            }
        }

        return maxLen;
    }

    private int lcsHelper(int row, int col, int[][] matrix, int[][] memo) {
        if (memo[row][col] != 0) {
            return memo[row][col];
        }

        int len = 0;

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int m = memo.length;
        int n = memo[0].length;

        for (int i = 0; i < 4; i++) {
            int nx = row + dirs[i][0];
            int ny = col + dirs[i][1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && 
                matrix[nx][ny] > matrix[row][col]) {
                len = Math.max(len, lcsHelper(nx, ny, matrix, memo));
            }
        }
        
        memo[row][col] = len + 1;

        return len + 1;
    }
}