# 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

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