Maximum Non Negative Product in a Matrix

Maximum Non Negative Product in a Matrix

문제 내용 : (0,0)에서 최소 거리 기준으로 (우측, 아래로만 이동 가능) 이동하면서 (row,col)까지의, Path의 값들을 곱한다고 했을 때 최대 값은 얼마인가? 음수로만 최대 값이 나온다면 -1을 return 한다.

접근 방법 : Dynamic-Programming-With-Comments (문제 해결 못해서 Contest 후 Comment를 보고 풀이 했다. 그래서 코드도 똑같다.)

가장 큰 값들로만 이루어진 Maximum Grid와

가장 작은 값들로 이루어진 Minimum Grid를 유지하고 최종적으로 Maximum Grid의 (row, col) 값으로 return하면 된다.

• 현재 값이 0보다 작은 경우
  • 가장 큰 값 : 좌측 그리고 상단 Cell에서 가장 작은 값을 곱하면 가장 큰 값이 된다.
    예) 좌측 5, 상단 -6라고 볼때 현재 값이 -1이면 -6 * -1이 가장 큰 값이 된다.
    예2) 좌측 9, 상단 1라고 볼때 현재 값이 -1이면 1 * -1이 가장 큰 값이 된다.
  • 가장 작은 값 : 좌측 그리고 상단 Cell에서 가장 큰 값을 곱하면 가장 작은 값이 된다.
    예) 좌측 5, 상단 -6라고 볼때 현재 값이 -1이면 5 * -1이 가장 작은 값이 된다.
    예2) 좌측 9, 상단 1라고 볼때 현재 값이 -1이면 9 * -1이 가장 작은 값이 된다.
• 현재 값이 1보다 큰 경우
  • 가장 큰 값 : 좌측 그리고 상단 Cell에서 가장 큰은 값을 곱하면 가장 큰 값이 된다.
    예) 좌측 5, 상단 -6라고 볼때 현재 값이 1이면 5 * 1이 가장 큰 값이 된다.
    예2) 좌측 9, 상단 1라고 볼때 현재 값이 1이면 9 * 1이 가장 큰 값이 된다.
  • 가장 작은 값 : 좌측 그리고 상단 Cell에서 가장 작은 값을 곱하면 가장 작은 값이 된다.
    예) 좌측 5, 상단 -6라고 볼때 현재 값이 1이면 -6 * 1이 가장 작은 값이 된다.
    예2) 좌측 9, 상단 1라고 볼때 현재 값이 1이면 1 * 1이 가장 작은 값이 된다.

var maxProductPath = function(grid) {
    let poArr = new Array(grid.length).fill(0).map(_ => new Array(grid[0].length).fill(0));
    let neArr = new Array(grid.length).fill(0).map(_ => new Array(grid[0].length).fill(0));

    for (let i = 0; i < grid.length; i++) {
        poArr[i][0] = grid[i][0] * (0 < i ? poArr[i - 1][0] : 1);
        neArr[i][0] = grid[i][0] * (0 < i ? neArr[i - 1][0] : 1);
    }

    for (let i = 0; i < grid[0].length; i++) {
        poArr[0][i] = grid[0][i] * (0 < i ? poArr[0][i - 1] : 1);
        neArr[0][i] = grid[0][i] * (0 < i ? neArr[0][i - 1] : 1);
    }


    for (let row = 1; row < grid.length; row++) {
        for (let col = 1; col < grid[0].length; col++) {
            if (grid[row][col] < 0) {
                // 마이너스는 가장 작은 값과 곱해지는 것이 최고 값이 된다.
                poArr[row][col] = Math.min(neArr[row - 1][col], neArr[row][col - 1]) * grid[row][col];
                // 마이너스에 가장 큰값을 곱하면 가장 작은 값이 된다.
                neArr[row][col] = Math.max(poArr[row - 1][col], poArr[row][col - 1]) * grid[row][col];
            } else {
                // 양수는 가장 큰 값과 곱해지는 것이 최고 값이 된다
                poArr[row][col] = Math.max(poArr[row - 1][col], poArr[row][col - 1]) * grid[row][col];
                // 양수는 가장 작은 값과 곱해지는 것이 최저가가 된다.
                neArr[row][col] = Math.min(neArr[row - 1][col], neArr[row][col - 1]) * grid[row][col];
            }
        }
    }
    return 0 <= poArr[grid.length-1][grid[0].length-1] ? poArr[grid.length-1][grid[0].length-1] % (Math.pow(10,9) + 7) : -1;
};