# Longest Increasing Continuous subsequence II ### Source - lintcode: [(398) Longest Increasing Continuous subsequence II](http://www.lintcode.com/en/problem/longest-increasing-continuous-subsequence-ii/) ### Problem 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. ### 題解 題 [Longest Increasing Continuous subsequence](http://algorithm.yuanbin.me/zh-cn/dynamic_programming/longest_increasing_continuous_subsequence.html) 的 follow up, 變成一道比較難的題了。從之前的一維 DP 變為現在的二維 DP，自增方向可從上下左右四個方向進行。需要結合 [DFS](# "Depth-First Search, 深度優先搜索") 和動態規劃兩大重量級武器。 根據二維 DP 的通用方法，我們首先需要關注狀態及狀態轉移方程，狀態轉移方程相對明顯一點，即上下左右四個方向的元素值遞增關系，根據此轉移方程，**不難得到我們需要的狀態為`dp[i][j]`——表示從坐標`(i, j)`出發所得到的最長連續遞增子序列。**根據狀態及轉移方程我們不難得到初始化應該為1或者0，這要視具體情況而定。 這里我們可能會糾結的地方在于自增的方向，平時見到的二維 DP 自增方向都是從小到大，而這里的增長方向卻不一定。**這里需要突破思維定勢的地方在于我們可以不理會從哪個方向自增，只需要處理自增和邊界條件即可。**根據轉移方程可以知道使用遞歸來解決是比較好的方式，這里關鍵的地方就在于遞歸的終止條件。比較容易想到的一個遞歸終止條件自然是當前元素是整個矩陣中的最大元素，索引朝四個方向出發都無法自增，因此返回1. 另外可以預想到的是如果不進行記憶化存儲，遞歸過程中自然會產生大量重復計算，根據記憶化存儲的通用方法，這里可以以結果是否為0(初始化為0時)來進行區分。 ### Java ~~~ public class Solution { /** * @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; int lics = 0; int[][] dp = new int[A.length][A[0].length]; for (int row = 0; row < A.length; row++) { for (int col = 0; col < A[0].length; col++) { if (dp[row][col] == 0) { lics = Math.max(lics, dfs(A, row, col, dp)); } } } return lics; } private int dfs(int[][] A, int row, int col, int[][] dp) { if (dp[row][col] != 0) { return dp[row][col]; } // increasing from xxx to up, down, left, right int up = 0, down = 0, left = 0, right = 0; // increasing from down to up if (row > 0 && A[row - 1][col] > A[row][col]) { up = dfs(A, row - 1, col, dp); } // increasing from up to down if (row + 1 < A.length && A[row + 1][col] > A[row][col]) { down = dfs(A, row + 1, col, dp); } // increasing from right to left if (col > 0 && A[row][col - 1] > A[row][col]) { left = dfs(A, row, col - 1, dp); } // increasing from left to right if (col + 1 < A[0].length && A[row][col + 1] > A[row][col]) { right = dfs(A, row, col + 1, dp); } // return maximum of up, down, left, right dp[row][col] = 1 + Math.max(Math.max(up, down), Math.max(left, right)); return dp[row][col]; } } ~~~ ### 源碼分析 [dfs](# "Depth-First Search, 深度優先搜索") 遞歸最深一層即矩陣中最大的元素處，然后逐層返回。這道題對狀態`dp[i][j]`的理解很重要，否則會陷入對上下左右四個方向的迷霧中。 ### 復雜度分析 由于引入了記憶化存儲，時間復雜度逼近 O(mn)O(mn)O(mn), 空間復雜度 O(mn)O(mn)O(mn). ### Reference - [Lintcode: Longest Increasing Continuous subsequence II | codesolutiony](https://codesolutiony.wordpress.com/2015/05/25/lintcode-longest-increasing-continuous-subsequence-ii/)