Space explorers arriving on an alien planet found a cave with two chambers. The cave contains n alien eggs, of a species they want to study. Egg i will hatch A[i, j] aliens if it is in the same chamber as egg j. If both eggs j and k are in the same chamber as i, i will hatch A[i, j] A[i, k] aliens, etc. Egg 1 is in chamber 1, egg n is in chamber 2, and neither egg can be safely moved. The rest of the eggs can be safely moved, so the explorers want to separate the alien eggs over the two chambers such that the resulting number of spawned aliens will be as large as possible. Required:
Give a polynomial-time algorithm to find the optimal partitioning of eggs into chambers, and explain your answer.