Solução escrita por Caique Paiva
Conhecimento prévio necessário:
Primeiro, veja que sabemos a área do retângulo original, basta somar as áreas de todos os retângulos que temos. Com isso, vamos considerar dois casos: Se o primeiro corte foi horizontal e se o primeiro corte foi vertical. Vamos resolver para o primeiro corte sendo horizontal, e o outro caso será análogo.
Como o primeiro corte foi horizontal, existe um retângulo com comprimento igual ao comprimento do retângulo original. Esse retângulo vai ser o retângulo com maior comprimento do nosso vetor. Sabendo o comprimento do retângulo e a sua área, podemos calcular a largura! Então, basta sabermos se podemos construir tal retângulo.
Vamos fazer o seguinte algoritmo: Seja $$h, w$$ a largura e o comprimento do retângulo, Suponha que temos um sub-retângulo $$ \{ h’, w’ \} $$ onde $$ h = h’$$ ou $$ w = w’$$ (Caso não exista, então não temos como construir o retângulo). Então, vamos tirar esse sub-retângulo, fazendo $$h -= h’$$ ou $$w -= w’$$. Paramos o algoritmo quando usarmos todos os sub-retângulos, retornando que o retângulo pode ter tamanho $$h, w$$.
A parte mais difícil desse problema é codar, então recomendo fortemente a você fazer seu próprio código antes de ler o código da solução. Veja o código nesse link.