Longest Continuous Increasing Subsequence 2D

1, Longest Continuous Increasing Subsequence

2, Longest Increasing Subsequence

3, Longest Continuous Increasing Subsequence 2D

1）对于每一个点，进行DFS，看其能连续增长的最长距离。普通的DFS思想。

2）加入MemSearch的思想，如果一个点已经被跑过，就不用再跑了，直接复用原来的结果。

/**
 * @param A an integer matrix
 * @return  an integer
 */

 vector<vector<bool>> flag;
 vector<vector<int>> dp;

int longestIncreasingContinuousSubsequenceII(vector<vector<int>>& A) {
    // Write your code here
    if(A.size() == 0)
    {
        return 0;
    }

    int m = A.size();
    int n = A[0].size();

    for(int i = 0; i<m; i++)
    {
        vector<bool> tmp(n, false);
        flag.push_back(tmp);
    }

    for(int i = 0; i<m; i++)
    {
        vector<int> tmp(n, 1);
        dp.push_back(tmp);
    }

    int ans = 0;
    for(int i = 0; i<m; i++)
    {
        for(int j = 0; j<n; j++)
        {
            dp[i][j] = search(A, i, j);
            ans = max(ans, dp[i][j]);
        }
    }

    return ans;
}

int search(const vector<vector<int>>& A, int x, int y)
{
    if(flag[x][y])
    {
        return dp[x][y];
    }

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    int ans = 1;
    for(int i = 0; i<4; i++)
    {
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx < 0 || nx >= A.size() || ny < 0 || ny >= A[0].size())
        {
            continue;
        }
        if(A[x][y] > A[nx][ny])
        {
            ans = max(ans, search(A, nx, ny) + 1);
        }
    }

    flag[x][y] = true;
    dp[x][y] = ans;

    return ans;

}