# Task

John won the championship of a TV show. He can get some bonuses.

He needs to play a game to determine the amount of his bonus.

Here are some cards in a row. A number is written on each card.

In each turn, John can take a card, but only from the beginning or the end of the row. Then multiply the number on the card by an coefficient 2^(i)(i means the ith turn). The product is John's bonus of current turn.

After all the cards are taken away, the game is over. John's final bonus is the sum of all rounds of bonuses.

Obviously, the order in which John takes the cards will affect the amount of John's final bonus.

Your task is to help John calculate the maximum amount of bonuses he can get.

# Input

- `cards`: An integer array. Each element represents the number on the card.
  - `1 <= cards.length <= 30`
  - `1 <= cards[i] <= 100`


- All inputs are valid.

# Output

An integer. the maximum amount of bonuses John can get.

# Eaxmple

For `cards=[1,2,5]`, the output should be `50`.

```
All possible orders are:
1->2->5   bonus:1x2+2*4+5*8=50
1->5->2   bonus:1x2+5*4+2*8=38
5->1->2   bonus:5*2+1*4+2*8=30
5->2->1   bonus:5*2+2*4+1*8=26
The maximum amount of bonus is 50.
```

Source: codewars | Difficulty: EASY
Tags: Dynamic programming

Starter code: def calc(cards):
	

Solutions:
def calc(a):
	res = [0] * (len(a) + 1)
	for k in range(len(a)):
		res = [2 * max(a[i] + res[i + 1], a[i + k] + res[i]) for i in range(len(a) - k)]
	return res[0]


from functools import lru_cache
calc = lambda cards: get(tuple(cards))
get = lru_cache(None)(lambda seq, turn=1: max([2 ** turn * seq[0] + get(seq[1:], turn + 1), 2 ** turn * seq[-1] + get(seq[:-1], turn + 1)]) if seq else 0)


from collections import deque, defaultdict

def calc(cards):
	memo = defaultdict(int)
	ans = 0
	q = deque([(1, 0, tuple(cards))])
	while q:
		(i, score, remains) = q.popleft()
		if len(remains) == 1:
			score += remains[0] * 2 ** i
			if score > ans:
				ans = score
		else:
			score_l = score + remains[0] * 2 ** i
			if score_l > memo[remains[1:]]:
				memo[remains[1:]] = score_l
				q.append((i + 1, score_l, remains[1:]))
			score_r = score + remains[-1] * 2 ** i
			if score_r > memo[remains[:-1]]:
				memo[remains[:-1]] = score_r
				q.append((i + 1, score_r, remains[:-1]))
	return ans


VISITED = dict()

def calc(cards, idx=0):
	if idx == 0:
		VISITED.clear()
	if len(cards) == 0:
		return 0
	tpl = tuple(cards)
	m_value = VISITED.get(tpl, None)
	if m_value:
		return m_value
	res = max(cards[0] * (2 << idx) + calc(cards[1:], idx + 1), cards[-1] * (2 << idx) + calc(cards[:-1], idx + 1))
	VISITED[tpl] = res
	return res


from sys import intern

def calc(cards, i=1, memo={}):
	if len(cards) == 1:
		memo[intern(str((i, cards)))] = cards[0] * 2 ** i
		return cards[0] * 2 ** i
	if str((i, cards)) in memo:
		return memo[intern(str((i, cards)))]
	result = max(cards[0] * 2 ** i + calc(cards[1:], i + 1, memo), cards[-1] * 2 ** i + calc(cards[:-1], i + 1, memo))
	memo[intern(str((i, cards)))] = result
	return result


def calc(cards):
	f = 1 << len(cards)
	dp = [f * v for v in cards]
	for d in range(1, len(cards)):
		f >>= 1
		dp = [max(dp[i] + f * cards[i + d], dp[i + 1] + f * cards[i]) for i in range(len(dp) - 1)]
	return dp.pop()


from functools import lru_cache as memo

def calc(cards):

	@memo(None)
	def get_value(i, j, n):
		if i == j:
			return cards[i] * 2 ** n
		return max(cards[i] * 2 ** n + get_value(i + 1, j, n + 1), cards[j] * 2 ** n + get_value(i, j - 1, n + 1))
	return get_value(0, len(cards) - 1, 1)


def calc(cards):
	queue = [(0, (0, len(cards) - 1))]
	counter = 1
	multiplier = 1
	global_max = 0
	while True:
		hold = {}
		for _ in range(counter):
			(bonus, indices) = queue.pop(0)
			if indices[0] > indices[1]:
				return global_max
			take_right = (indices[0], indices[1] - 1)
			bonus_right = bonus + cards[indices[1]] * 2 ** multiplier
			take_left = (indices[0] + 1, indices[1])
			bonus_left = bonus + cards[indices[0]] * 2 ** multiplier
			if take_left in hold:
				hold[take_left] = max(hold[take_left], bonus_left)
			else:
				hold[take_left] = bonus_left
			if take_right in hold:
				hold[take_right] = max(hold[take_right], bonus_right)
			else:
				hold[take_right] = bonus_right
			global_max = max(global_max, bonus_left, bonus_right)
		queue.extend([(hold[cards], cards) for cards in hold])
		counter += 1
		multiplier += 1
	return global_max


def calc(cards):
	n = len(cards)
	table = [[-1 for i in range(n)] for j in range(n)]
	high = n - 1

	def score(low, high, i):
		if i == n:
			return 2 ** i * cards[low]
		elif table[low][high] != -1:
			return table[low][high]
		else:
			max_score = max(score(low + 1, high, i + 1) + 2 ** i * cards[low], score(low, high - 1, i + 1) + 2 ** i * cards[high])
			table[low][high] = max_score
			return max_score
	return score(0, high, 1)


def calc(a):
	res = [0] * (len(a) + 1)
	for k in range(1, len(a) + 1):
		new_res = []
		new_res_size = len(res) - 1
		for i in range(new_res_size):
			j = i + k
			new_res.append(2 * max(a[i] + res[i + 1], a[j - 1] + res[i]))
		res = new_res
	return res[0]