Longest Increasing Continuous subsequence II

http://www.lintcode.com/en/problem/longest-increasing-continuous-subsequence-ii/

记忆化搜索；

核心：下一个dfs节点不会回到上一个dfs的节点；

class Solution {


public:
    /**
     * @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;
    }
};