Esse problema é semelhante ao problema maior subsequência crescente . Digamos que armazenemos o número de livros dentro de cada estante de livros em uma matriz N.
N[i] = number of books in bookcase i.
Você mantém uma matriz S, onde S [i] é o valor máximo que você pode obter para a outra sala usando um subconjunto dos itens 1 a i que contém o item i.
S[ 1 ] = N[ 1 ]
S[ i ] = max( S[ 1 ], S[ 2 ], ... S[ i - 2 ] ) + N[ i ], for i = 3..N.Size
A resposta será então o valor max(S[N.Size], S[N.Size - 1]) . Para obter os itens reais que você pega, você pode manter informações adicionais em outra matriz PREV [i] - O item antes de eu na nova sala.
Isso é executado em O (n ^ 2) tempo, mas você pode melhorar isso para O (nlogn) usando árvores de intervalo ou indexadas binárias para obter o máximo em tempo logarítmico (semelhante ao maior problema de subsequência crescente)
Atualização: Apenas percebi que, se os valores forem positivos, podemos resolver isso em O (n)
S[i] =max(S[i-2], S[i-3]) + N[i]
Mas, se os valores puderem ser negativos, isso não funcionará