Animals with labels outside the interval [lower,upper] serve as obstacles that divide the line into groups.
It makes no sense to take just a part of the group -- if we take some animals from the group, we
might as well take them all, there is no penalty in doing that.
For each group, make a bitmask that represents the animal labels present in the group.
As there are at most 44 animals, there can be at most 22 groups, which means that we can now
use brute force to try all sets of groups and pick the best one.

In general, this solution would be O(poly(n)*2^(n/2)) where n is the number of animals.
Faster solutions are possible. For example, you could consider groups that consist
of a single animal separately, and only use brute force for the larger groups.
This brings the time complexity down to O(poly(n)*2^(n/3)).