Longest Increasing Continuous subsequence II

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.

Thoughts

滑雪问题，这一题没法用DP做，要做记忆化搜索

1. 初始化很麻烦，找不到合适的初始化条件
2. 中间状态之间的关系比较复杂，不像dp是有一个清晰的顺序

用一个flag matrix保存已经计算的过的位置，用dp matrix记录结果 dp[i][j]表示以matrix[i][j]为结尾的longest increasing continuous subsequence的值

Solution

class Solution:
    # @param {int[][]} A an integer matrix
    # @return {int}  an integer

    def longestIncreasingContinuousSubsequenceII(self, A):
        # Write your code here        
        if not A:
            return 0
        rowNum = len(A)
        colNum = len(A[0])
        flag = [[False for i in range(colNum)] for j in range(rowNum)]
        dp = [[1 for i in range(colNum)] for j in range(rowNum)]
        self.dx = [1,-1,0,0]
        self.dy = [0,0,1,-1]
        result = 1
        for i in range(rowNum):
            for j in range(colNum):
                dp[i][j] = self.search(i, j, A, flag, dp)
                result = max(result, dp[i][j])

        return result

    def search(self, x, y, A, flag, dp):
        if flag[x][y]:
            return dp[x][y]

        ans = 1
        for i in range(4):
            nx = x + self.dx[i]
            ny = y + self.dy[i]
            if nx >= 0 and nx < len(A) and ny >= 0 and ny < len(A[0]):
                if A[x][y] > A[nx][ny]:
                    ans = max(ans, self.search(nx,ny,A, flag, dp) + 1)

        flag[x][y] = True
        dp[x][y] = ans
        return ans