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

• 状态

• `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);
}
}``````

Last updated