# 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.
```
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
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