The greedy choice above may seem reasonable, but give a small, but non-trivial counterexample where this approach is sub-optimal, and describe an optimal solution for this

counterexample which may be obtained by some other strategy.

"My love for you is like a large fries" Suppose vou are on a date with a potential partner at a fast-food ioint and have ordered a large fries to share. The n fries in the container all have distinct lengths You each take turns eating fries, and being the thoughtful individual you are, you allow your date to eat the first fry. Assume your date is very modest and always eats one fry oin his/her turn, but always chooses the longest fry. On your turn, you can eat any number of fries Definitions: l: length of fry fi Ld: sum total length of fries eaten by your date * Ly: sum total length of fries eaten by you . Gd: goodwill of your date, computed as Ld - Ly You want to maximise your own value of Ly, but you also want to avoid any negative will from your date. Thus, by the time the fries are completely finished, you want to have eaten a set of fries complementing those eaten by your date that keeps Gd to a positive number as close (or equal) to zero as possible One greedy approach is the following: while there exists a fry which can be eaten to keep Gd eat the longest fry which keeps Gd 2 0 end while end your turn "My love for you is like a large fries" Suppose vou are on a date with a potential partner at a fast-food ioint and have ordered a large fries to share. The n fries in the container all have distinct lengths You each take turns eating fries, and being the thoughtful individual you are, you allow your date to eat the first fry. Assume your date is very modest and always eats one fry oin his/her turn, but always chooses the longest fry. On your turn, you can eat any number of fries Definitions: l: length of fry fi Ld: sum total length of fries eaten by your date * Ly: sum total length of fries eaten by you . Gd: goodwill of your date, computed as Ld - Ly You want to maximise your own value of Ly, but you also want to avoid any negative will from your date. Thus, by the time the fries are completely finished, you want to have eaten a set of fries complementing those eaten by your date that keeps Gd to a positive number as close (or equal) to zero as possible One greedy approach is the following: while there exists a fry which can be eaten to keep Gd eat the longest fry which keeps Gd 2 0 end while end your turn