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 
a largura e o comprimento do retângulo, Suponha que temos um sub-retângulo 
onde 
ou 
(Caso não exista, então não temos como construir o retângulo). Então, vamos tirar esse sub-retângulo, fazendo 
ou 
. Paramos o algoritmo quando usarmos todos os sub-retângulos, retornando que o retângulo pode ter tamanho .
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.