board размером m × n, в каждой клетке записано целое число. Фишка стоит в левом верхнем углу и за один ход сдвигается на клетку вправо или вниз, пока не дойдёт до правого нижнего угла.
Произведение пути — это произведение чисел во всех клетках, через которые прошла фишка, включая начальную и конечную. Найдите наибольшее неотрицательное произведение среди всех путей и верните его по модулю 10⁹ + 7. Если у всех путей произведение отрицательное, верните -1.
Обратите внимание: максимум выбирается по настоящим значениям произведений, а остаток от деления берётся уже от найденного максимума.board=[[2, -1, 3], [-2, 4, -1]] → 16
Путь 2 → -1 → 3 → -1 даёт 6, путь 2 → -1 → 4 → -1 — 8, а путь 2 → -2 → 4 → -1 — 16. Больше получить нельзя.
board=[[3, -2], [1, 2]] → 6
Есть только два пути: 3 · (-2) · 2 = -12 и 3 · 1 · 2 = 6. Ответ 6.
board=[[-1, 2], [3, 4]] → -1
Оба пути начинаются с -1, а дальше идут только положительные числа, поэтому любое произведение отрицательно: ответ -1.
board[i][j] ≤ 4board=[[2, -1, 3], [-2, 4, -1]]
16
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 65 тестов на сервере, включая скрытые.