Longest Line of Consecutive One in Matrix

Description

null

Solution(javascript)

// /** 1: 注意两种对角戏
//  * @param {number[][]} M
//  * @return {number}
//  */
// const longestLine = function (M) {
//   let max = 0
//   const dp = M.map(items => items.map(() => [0, 0, 0, 0]))
//   const getValue1 = (row, column) => {
//     if (row < 0 || column < 0 || row >= M.length || column >= M[row].length) {
//       return [0, 0, 0, 0]
//     }
//     return dp[row][column]
//   }
//   for (let i = 0; i < M.length; i++) {
//     for (let j = 0; j < M[i].length; j++) {
//       if (M[i][j] === 1) {
//         dp[i][j] = [
//           getValue1(i, j - 1)[0] + 1,
//           getValue1(i - 1, j)[1] + 1,
//           getValue1(i - 1, j - 1)[2] + 1,
//           getValue1(i - 1, j + 1)[3] + 1,
//         ]
//       }
//       max = Math.max(max, ...dp[i][j])
//     }
//   }
//   return max
// }

/** 2: 注意两种对角戏
 * @param {number[][]} M
 * @return {number}
 */
const longestLine = function (M) {
  let max = 0
  let dp = []
  const getValue1 = (column, arr = dp) => {
    if (!arr[column]) {
      return [0, 0, 0, 0]
    }
    return arr[column]
  }
  for (let i = 0; i < M.length; i++) {
    const current = []
    for (let j = 0; j < M[i].length; j++) {
      if (M[i][j] === 1) {
        current[j] = [
          getValue1(j - 1, current)[0] + 1,
          getValue1(j)[1] + 1,
          getValue1(j - 1)[2] + 1,
          getValue1(j + 1)[3] + 1,
        ]
        max = Math.max(max, ...current[j])
      }
    }
    dp = current
  }
  return max
}