> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/dynamic_programming/longest_increasing_continuous_subsequence_ii.md).

# 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

```java
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](http://www.jiuzhang.com/solutions/longest-increasing-continuous-subsequence-ii/)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/dynamic_programming/longest_increasing_continuous_subsequence_ii.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.