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.

Tags

Dynamic Programming

Related Problems

Easy Longest Increasing Continuous Subsequence

Analysis

可以借鉴在I问题中的思路，来构建2D的状态转移方程。

在2D中搜索increasing continuous subsequence, 可以考虑双重循环加递归搜索，直接求以(x, y)为结尾的最长子序列。

利用记忆化搜索可以进行优化。

什么时候用记忆化搜索? 1. 状态转移特别麻烦，不是顺序性。 2. 初始化状态不是很容易找到。

动态规划求解四要素：

• 状态

  • dp[x][y]： 以x, y作为结尾的最长子序列

• 方程

  • 遍历x, y上下左右四个方向的格子

  • dp[x][y] = dp[nx][ny] + 1 if A[x][y] > A[nx][ny]

• 初始化

  • dp[x][y]是极小值时，初始化为1

• 答案

  • d[x][y]中的最大值

Solution

public class Solution {
    int[][] dp;
    int[][] flag;
    int M, N;

    int[] dx = new int[] {-1, 0, 1, 0};
    int[] dy = new int[] {0, -1, 0, 1};
    /**
     * @param A an integer matrix
     * @return  an integer
     */
    public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        if (A == null || A.length == 0 || A[0].length == 0) {
            return 0;
        }
        M = A.length;
        N = A[0].length;
        dp = new int[M][N];
        flag = new int[M][N];

        int ans = 0;

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                dp[i][j] = search(i, j, A);
                ans = Math.max(ans, dp[i][j]);
            }
        }

        return ans;
    }

    // Memorized search, recursive
    public int search(int x, int y, int[][] A) {
        if (flag[x][y] != 0) {
            return dp[x][y];
        }

        int ans = 1; // Initialize dp[x][y] = 1 if it's local min compare to 4 directions
        int nx, ny;
        for (int i = 0; i < dx.length; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (insideBoundary(nx, ny) && (A[x][y] > A[nx][ny])) {
                ans = Math.max(ans, search(nx, ny, A) + 1);
            }
        }

        flag[x][y] = 1;
        dp[x][y] = ans;

        return ans;
    }

    public boolean insideBoundary(int x, int y) {
        return (x >=0 && x < M && y >= 0 && y < N);
    }
}

Reference

• Jiuzhang: Longest Increasing Continuous subsequence II