How to approach Gold grid?[hp]

#1

how to approach this problem , and also in this problem we get only smallest size of rectange ?

#2

@dhruv.160410116084 Just take prefix sum of every row and after that take prefix sum of every column.
Then if you partition the (i,j)th of grid then your top-left box sum will be the value at (i,j)th index of grid
and top-right box sum will be the sum at that row’s last column - the sum of top-left box sum
and bottom right box sum will be the value at (n,j)th of grid - the sum of top-left box
and bottom-right box sum will be the value at (n,m)th of grid - top-right box sum - bottom left box sum + the sum of top-left box ( because it get subtracted two times , first time in top-right box sum and second time in bottom-left box sum ).
Make ans at every step as
ans = max ( ans, min( all four boxes) );

1 Like