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

return25

Challenge

O(nm) time and memory.

line 37 , need to talk with interviewer about equal value case

class Solution {

public:

/**

 * @param A an integer matrix

 * @return  an integer

 */

int longestIncreasingContinuousSubsequenceII(vector<vector<int>>& A) {

    // Write your code here

    if (A.empty() || A[0].empty()) {

        return 0;

    }

    int n = A.size();

    int m = A[0].size();

    vector<vector<int>> f(n, vector<int>(m, 1));

    vector<vector<bool>> flag(n, vector<bool>(m, false));

    int longest = 1;

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < m; ++j) {

            if (flag[i][j] == false) {

                f[i][j] = search(i, j, A, flag, f);

            }

            longest = max(longest, f[i][j]);

        }

    }

    return longest;

}
private:

int search(int i, int j, vector<vector<int>>& A, vector<vector<bool>>& flag, vector<vector<int>>& f) {

    int n = A.size();

    int m = A[0].size();

    int len = 1;

    static vector<vector<int>> dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};

    for (auto dir : dirs) {

        int nx = i + dir[0];

        int ny = j + dir[1];

        if (nx < 0 || nx >= n || ny < 0 || ny >= m || A[i][j] >= A[nx][ny]) {

            continue;

        }

        if (flag[nx][ny] == false) {

            f[nx][ny] = search(nx, ny, A, flag, f);

        }

        len = max(len, 1 + f[nx][ny]);

    }

    flag[i][j] = true;

    return len;

}
};