I recently had a Google interview where they asked a dynamic programming question that I was not able to fully get. The question goes as follows:

To thank you for solving the game, your friend gives you a large chessboard as a gift.
Unfortunately, the board has been assembled incorrectly, and some adjacent cells have the same color.

Additionally, the board is rectangular, and has width m and height n. As you like to avoid waste, you decide to fix the board.

A correct board has the following properties:

• its width is equal to its height
• no two adjacent cells of the board have the same color

You would like to fix the board to extract a maximum correct sub-board out of the original board.
This may involve flipping the colors of some cells, i.e., inverting the color from white to black or from black to white.

More formally, given an arbitrary m × n input board, you must preprocess the board using an efficient algorithm that you design. After preprocessing, given a query w indicating the number of cells that you wish to flip, your algorithm must output the maximum size of a correct chessboard that can be constructed using at most w flips in O(1) time.

You can assume that m = Θ(n) for simplicity (note that this does not mean that they are exactly equal).
Give a preprocessing algorithm that runs in O(n^3).

Argue that the overall query algorithm is correct and runs in the required time. Give a proof of correctness as well.

Any ideas on how to solve this question it really stumped me. Thanks in advance!