The Largest Product Across
Walk from the top-left cell to the bottom-right cell, moving only RIGHT or DOWN. A path's value is the PRODUCT of every cell it visits, including both ends.
Print the largest product, modulo 1000000007. If every path has a negative product, print
-1.
1 -2 1
1 -2 1 -> 8
3 -4 1
## Why one number per cell is not enough
For sums, the best total reaching a cell extends to the best total onward, so one number per cell suffices.
Products break that. Multiplying by a NEGATIVE value turns the largest product into the smallest and the smallest into the largest. So the best product ending at a cell can come from the WORST product at its predecessor.
Tracking only the maximum discards exactly the value that a later negative would need.
## Carry both extremes
mx[r][c] = the largest product reaching (r, c)
mn[r][c] = the smallest product reaching (r, c)
For each predecessor, form both mx * v and mn * v, collect all the candidates, and take
the maximum for mx and the minimum for mn:
candidates = { mx[above] * v, mn[above] * v, mx[left] * v, mn[left] * v }
mx[r][c] = max(candidates)
mn[r][c] = min(candidates)
Both must be computed from the SAME candidate set. Computing mx from maxima only and
mn from minima only is the natural-looking mistake and it is wrong for the same reason the
single value was.
This is the grid form of the maximum-product-subarray idea, and the general lesson is that when an operation can REORDER the comparison, the state must carry both ends of the range.
## Zeros
A zero makes the product zero, and zero is neither positive nor negative. The same recurrence handles it: both extremes become 0 and any later multiplication keeps them at 0.
1 3 / 0 -4 answers 0: the best path goes through the zero, which beats the negative
alternative.
That input matters because the answer 0 must be printed as 0 rather than -1, and it is
only reached by noticing that 0 is not negative.
## The negative case
If the largest product is still negative, no path qualifies and the answer is -1.
-1 -2 -3 / -2 -3 -3 / -3 -3 -2 answers -1, and so does 1 -1 / -1 1, where both paths
give -1. Note that the second grid CONTAINS positive values and still answers -1, which
rules out any shortcut based on counting negatives in the grid.
## Bounds
The path visits m + n - 1 cells, at most 29 here, each with absolute value at most 4. So
the largest magnitude is 4^29, about 2.9 * 10^17, which fits in a signed 64-bit integer
with room to spare.
Take the modulus only at the very END, after deciding the sign. Reducing along the way destroys the comparison, since a reduced value no longer orders like the real one.
That ordering is the reason the constraints are small: they exist so the products stay exact until the final step.
## Cost
Time O(m n). Space O(m n), reducible to O(n) with two rows.