5 kyu

Kata 2019: Bonus Game I

71 of 183myjinxin2015

Description:

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 2i(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.
Algorithms
Dynamic Programming

Stats:

CreatedJan 3, 2019
PublishedJan 3, 2019
Warriors Trained1020
Total Skips38
Total Code Submissions2904
Total Times Completed183
JavaScript Completions71
Python Completions116
Haskell Completions11
Total Stars44
% of votes with a positive feedback rating97% of 48
Total "Very Satisfied" Votes46
Total "Somewhat Satisfied" Votes1
Total "Not Satisfied" Votes1
Total Rank Assessments9
Average Assessed Rank
5 kyu
Highest Assessed Rank
4 kyu
Lowest Assessed Rank
7 kyu
Ad
Contributors
  • myjinxin2015 Avatar
  • JohanWiltink Avatar
  • Just4FunCoder Avatar
  • saudiGuy Avatar
Ad