[lintcode] Longest Increasing Continuous subsequence II


Longest Increasing Continuous subsequence II

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

Have you met this question in a real interview?

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

dp + BFS.

Use a dp 2d array to store the length of maximum increasing continues subsequence starting from current cell.

class Solution {
public:
    /**
     * @param A an integer matrix
     * @return  an integer
     */
    int longestIncreasingContinuousSubsequenceII(vector<vector<int>>& A) {
        // Write your code here
        int ans = 0;
        if(A.size() == 0 || A[0].size() == 0) return 0;
        vector<vector<int>> dp = vector<vector<int>>(A.size(), vector<int>(A[0].size(), 0));
        for(int i = 0; i < A.size(); i++){
            for(int j = 0; j < A[0].size(); j++){
                int length = BFS(A, dp, i, j);
                ans = max(length, ans);
            }
        }
        return ans;
    }
    int BFS(vector<vector<int>>& A, vector<vector<int>>& dp, int i, int j){
        int dict[][2] = {{0, 1}, {0 , -1}, {1, 0}, {-1, 0}};
        if(dp[i][j] != 0){
            return dp[i][j];
        }
        dp[i][j] = 1;
        for(int k = 0; k < 4; k++){
            int ni = i + dict[k][0];
            int nj = j + dict[k][1];
            // out of index
            if(ni < 0 || nj < 0 || ni >= A.size() || nj >= A[0].size()){
                continue;
            }
            // not increasing
            if(A[ni][nj] <= A[i][j]){
                continue;
            }
            int length = BFS(A, dp, ni, nj);
            dp[i][j] = max(dp[i][j], length + 1);
        }
        return dp[i][j];
    }
};

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.