C++ O(mn) time, O(n) space DP solution


  • 0
    M
        int longestLine(vector<vector<int>>& M) {
            if(M.size()==0||M[0].size()==0) return 0;
            vector<vector<int>> dp(M.size(), vector<int>(4, 0));
            int len=0;
            for(int i=0;i<M.size();i++) {
                if(M[i][0]==1) {
                    dp[i][0]=1, dp[i][1]=1, dp[i][2]=1, dp[i][3]=1;
                    if(i>0) dp[i][0]+=dp[i-1][0];
                }
                len=max(len, dp[i][0]);
            }
            for(int i=1;i<M[0].size();i++) {
                vector<vector<int>> dp1(M.size(), vector<int>(4, 0));
                for(int j=0;j<M.size();j++) {
                    if(M[j][i]==1) {
                        dp1[j][0]=1, dp1[j][1]=1+dp[j][1], dp1[j][2]=1, dp1[j][3]=1;
                        if(j>0) dp1[j][0]+=dp1[j-1][0];
                        if(j>0) dp1[j][2]+=dp[j-1][2];
                        if(j<M.size()-1) dp1[j][3]+=dp[j+1][3];
                    }
                    len=max(len, max(max(dp1[j][0], dp1[j][1]), max(dp1[j][2], dp1[j][3])));
                }
                dp=dp1;
            }
            return len;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.