Help with a question

#1

Hi,
Wanted some hint with this question. What can be the thinking process specifically when it comes to dynamic programming?

#2

Hey @nik72619c
So think in terms of breaking the problem into sub problems .

Appproach
Lets max_x[i][j] denote the length of 1s in the same row i starting from (i,j).

So our current max with one end of the rectangle at (i,j) would be max_x[i][j].
As we move to the next row, there are 2 cases :

  1. max_x[i+1][j] >= max_x[i][j] which means that we can take max_x[i][j] 1s from next column as well and extend our current rectangle as it is, with one more extra row.
    11100000 - 111
    11111100 - 111

  2. max_x[i+1][j] < max_x[i][j] which means that if we want to extend our current rectangle to next row, we need to reduce the number of columns in it to max_x[i+1][j]
    11100000 - 11
    11000000 - 11

As mentioned above, we keep increasing the columns and adjusting the width of the rectangle.

#3

Hey @nik72619c
Since u havent replied to this thread , I am closing this.
Refer this code if required : https://ide.codingblocks.com/s/351980 :slight_smile:

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.