发布于 2015-12-30 02:26:45 | 306 次阅读 | 评论: 0 | 来源: PHPERZ

这里有新鲜出炉的精品教程，程序狗速度看过来！

Leetcode 在线编程网站

leetcode 是一个美国的在线编程网站，上面主要收集了各大IT公司的笔试面试题，对于应届毕业生找工作是一个不可多得的好帮手。

---

Longest Increasing Continuous Subsequence II

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.

分析

这题非常像经典的滑雪问题，解决方法都是DFS + Memorization. dp[i][j]表示以点(i, j)为起始点的连续子序列最大长度。dp[i][j]的值可以根据其符合要求的邻居的dp值推出，根据dp值，我们维护一个全局的最大值，具体见代码。

复杂度

time: O(mn), space: O(mn)

代码

public class Solution {
    public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        int rows = A.length;
        if (rows == 0) 
            return 0;
        int cols = A[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int[][] dp = new int[rows][cols];
        int max = 1;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dp[i][j] == 0) 
                    dfs(A, visited, dp, i, j);
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
    
    public void dfs(int[][] A, boolean[][] visited, int[][] dp, int row, int col) {
        if (visited[row][col]) 
            return;
        visited[row][col] = true;
        int[][] dirs = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        int max = 0;
        
        // 对符合要求的邻居分别DFS
        for (int i = 0; i < dirs.length; i++) {
            int x = row + dirs[i][0];
            int y = col + dirs[i][1];
            if (x >= 0 && x < dp.length && y >= 0 && y < dp[0].length && A[x][y] > A[row][col]) {
                dfs(A, visited, dp, x, y);
                max = Math.max(max, dp[x][y]);
            }
        }
        dp[row][col] = max + 1; // 根据邻居DFS后最大值更新自己的值
    }
}