The algorithm is simple and you can use memoization and dynamic programming in this way:
def findMax(mem, cards, myTurn):
maxValue = 0
if(not cards):
return 0
if str(cards) in mem: #If we have already compute this state
return mem[str(cards)]
elif not myTurn: #turn of Elmo
if cards[0] > cards[len(cards) - 1]:
maxValue = findMax(mem, cards[1:], True)
else:
maxValue = findMax(mem, cards[:-1], True)
else: #your turn
maxValue = max(cards[0] + findMax(mem, cards[1:], False), cards[len(cards) - 1] + findMax(mem, cards[:-1], False))
mem[str(cards)] = maxValue #Store the max value for this state
return maxValue
import random
size = int(10 + random.randint(0,1))
cards = [random.randint(0,50) for x in range(size)]
print "Cards" + str(cards)
print findMax({}, cards, True)
Output:
Cards: [28, 33, 48, 0, 26, 1, 3, 11, 22, 32, 12]
Max value: 120