Longest Increasing Continuous subsequence II

Longest Increasing Continuous subsequence II

20%

Accepted

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

public class Solution {

    /**

     * @param A an integer matrix

     * @return  an integer

     */

    public int longestIncreasingContinuousSubsequenceII(int[][] A) {

        // Write your code here

        if(A == null || A.length == 0 || A[0].length == 0) return 0;

        int [][] store = new int[A.length][A[0].length];

        int res = 0;

        for(int i = 0; i < A.length; i++){

            for(int j = 0; j < A[0].length; j++){

                if(store[i][j] == 0){

                    res = Math.max(res, dfs(store, i, j, A));

                }

            }

        }

        return res;

    }

    

    private int dfs(int[][] store, int i, int j, int[][] A){

        if(store[i][j] != 0) return store[i][j];

        

        int left = 0, right = 0, up = 0, down = 0;

        if(j+1 < store[0].length && A[i][j+1] > A[i][j]){

            down = dfs(store, i, j+1, A);

        }

        if(j > 0  && A[i][j-1] > A[i][j]){

            up = dfs(store, i, j-1, A);

        }

        if(i+1 < store.length && A[i+1][j] > A[i][j]){

            right = dfs(store, i+1, j, A);

        }

         if(i > 0 && A[i-1][j] > A[i][j]){

            left = dfs(store, i-1, j, A);

        }

        store[i][j] = Math.max(Math.max(left, right), Math.max(up, down)) + 1;

        return store[i][j];

    }

}