// Time:  O(m * n)
// Space: O(n)

class Solution {
public:
    int longestLine(vector<vector<int>>& M) {
        if (M.empty()) {
            return 0;
        }
        int result = 0;
        vector<vector<vector<int>>> dp(2, vector<vector<int>>(M[0].size(), vector<int>(4)));
        for (int i = 0; i < M.size(); ++i) {
            for (int j = 0; j < M[0].size(); ++j) {
                dp[i % 2][j][0] = dp[i % 2][j][1] = dp[i % 2][j][2] = dp[i % 2][j][3] = 0;
                if (M[i][j] == 1) {
                    dp[i % 2][j][0] = j > 0 ? dp[i % 2][j - 1][0] + 1 : 1;
                    dp[i % 2][j][1] = i > 0 ? dp[(i - 1) % 2][j][1] + 1 : 1;
                    dp[i % 2][j][2] = (i > 0 && j > 0) ? dp[(i - 1) % 2][j - 1][2] + 1 : 1;
                    dp[i % 2][j][3] = (i > 0 && j < M[0].size() - 1) ? dp[(i - 1) % 2][j + 1][3] + 1 : 1;
                    result = max(result, max(dp[i % 2][j][0], max(dp[i % 2][j][1], max(dp[i % 2][j][2], dp[i % 2][j][3]))));
                }
            }
        }
        return result;
    }
};