Longest Increasing Continuous subsequence II

本是古典何须时尚 2021-12-17 10:27 114阅读 0赞

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

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`

Lintcode上的一题，这题很有意思，要求是二维矩阵里面连续递增的子序列．连续是在矩阵的四个方向都可以．如示例是在矩阵的外圈绕了一圈．和最长递增子序列类似．我们定义这里的dp状态为dp\[i\]\[j\]为以i,j为结尾的最长连续递增子序列的长度．

所以可以得出递推关系：dp\[i\]\[j\] = max\{dp\[i-1\]\[j\]+1(A\[i-i\]\[j\]<A\[i\]\[j\]), dp\[i\]\[j-1\]+1(A\[i\]\[j-1\] < A\[i\]\[j\]), dp\[i+1\]\[j\]+1(A\[i+1\]\[j\]<A\[i\]\[j\]), dp\[i\]\[j+1\]+1(A\[i\]\[j+1\]<A\[i\]\[j\])即在上下左右四个方向上进行递推．

初始化dp\[i\]\[j\] = 1, 即当前字符．

最终状态max(dp\[i\]\[j\]).既然dp\[i\]\[j\]定义的是以某个位置结束的最长递增子序列的长度．则矩阵中一共有m\*n个元素，则遍历完这些元素就可以．复杂度为Ｏ(n^2),这题因为初始化长度就是１，也有可能此处的最长长度就是１，所以用一个dp矩阵同时发挥visited矩阵很困难．需要另外设立一个flag矩阵．

代码如下：

class Solution:
        # @param {int[][]} A an integer matrix
        # @return {int}  an integer
        def longestIncreasingContinuousSubsequenceII(self, A):
            if not A or not A[0]:
                return 0
            n = len(A)
            m = len(A[0])
            flag = [[False]*m for i in xrange(n)]
            dp = [[1]*m for i in xrange(n)]
            maxVal = 1
            for i in xrange(n):
                for j in xrange(m):
                    maxVal = max(maxVal, self.search(A, flag, dp, i, j))
            return maxVal
        def search(self, A, flag, dp, x, y):
            if flag[x][y]:
                return dp[x][y]
            dx = [0, 0, -1, 1]
            dy = [1, -1, 0, 0]
            
            for i in xrange(4):
                if 0 <= x + dx[i] < len(A) and 0 <= y+dy[i] < len(A[0]) and A[x][y] > A[x+dx[i]][y+dy[i]]:
                    dp[x][y] = max(dp[x][y], self.search(A, flag, dp, x+dx[i], y+dy[i])+1)
            flag[x][y] = True
            return dp[x][y]

转载于:https://www.cnblogs.com/sherylwang/p/5616824.html