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

Difficulty: introductory

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)] # stores intermediate highest score
    high = n - 1

    def score(low, high, i):
        # base case 
        if (i == n):
            return 2**i * cards[low]
        # looks up if we have already calculated highest score
        elif (table[low][high] != -1): 
            return table[low][high]
        # recursive case
        else:
            max_score =  max( score(low+1, high, i+1) + 2**i * cards[low] ,  # pick card on the left, LOW
                            score(low, high-1, i+1) + 2**i * cards[high] )   # pick card on the right, HIGH
            table[low][high] = max_score

            return max_score

    return score(0, high, 1)

def calc(a):
    # k = 0
    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]