550. 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.

Constraints - `1 ≤ m ≤ 15` - `1 ≤ n ≤ 15` - `-4 ≤ value ≤ 4`