Wednesday, November 3, 2010

Alice and Bob play with an array

Alice and Bob play with an array of integers. In turn, each one can pop a number from one of the two ends of the array. What strategy can be used to maximize the sum of popped integers for Alice?


  1. Just pop randomly each turn ? I don't get the question, please explain!

  2. It's certainly not the obvious greedy strategy of take the biggest of the two ends... counterexample is 1 1 99 2

    It can definitely be solved by a 2D dynamic program which computes the score of an array [i..j]. S[i, j] is equal to max(a[i]-S[i+1, j], a[j]-S[j-1]), and S[i,i]=a[i]. (hmm, that doesn't tell you Alices actual score, just which decision will lead you to it.)

    I wonder if there's some fun goofy rule like adding all odd numbers and comparing to all even numbers and not immediately jumping into dynamic programming.