A train is given to two children as a gift. A train consists of a sequence of cars connected in a single line. There is an even number of cars, and the two children wish to divide them up. They do this by taking one car at a time from one end of the train. The older child goes first. Each car has a value to each child. and they want to maximize the value of the cars that they select. Note that the same car could be valued differently by the two children. Develop an algorithm for finding the best strategy for each child. The time complexity of your algorithm must be at most quadratic in the number of cars. If there happens to be a situation where the two choices for a child have the same value, then the child will make the choice which is best for the other child.
I am trying to figure this dynamic programming problem. I have a slight idea. I was thinking that the problem is reducible to knapsack problem but my confusion is about when the second child picks up the car.