Program to find out the maximum points collectable in a game in Python

Suppose we are playing a game of cards. We are given several cards arranged linearly with a number on each of them. The numbers on the cards are randomly distributed; and at the beginning and the end of the cards, two cards are inserted with the number 1 on them. Now, in the game, we have to collect the maximum points by picking up the given cards. The cards are represented in an array 'cards' where the elements in the array represent the number of cards[i]. When we pick up card i, we collect points cards[i - 1] * cards[i] * cards[i + 1]. When we pick up a card, cards[i - 1] and cards[i] become neighbors. So, from these given cards we find out the maximum points that we can collect.

So, if the input is like cards = [7, 5, 9, 10], then the output will be 1025

So in the game, we can pick up −

The card at index 1 and get 7 * 5 * 9 = 315 points.

The card at the new index 1 and get 7 * 9 * 10 = 630 points.

The card at index 1 and get 7 * 10 = 70 points.

The last card and get 10 points.

Total points = 315 + 630 + 70 + 10 = 1025

To solve this, we will follow these steps −

• Define a function search() . This will take x, y
  • temp := 0
  • for z in range x + 1 to y, do
    • temp := maximum of (temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y])
  • return temp
• insert values 1 and 1 at the beginning and the end of the list cards respectively
• return search(0, size of cards - 1)

Example

Let us see the following implementation to get better understanding −

def solve(cards):    def search(x, y):       temp = 0       for z in range(x + 1, y):          temp = max(temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y])       return temp    cards = [1] + cards + [1]    return search(0, len(cards) - 1) print(solve([7, 5, 9, 10]))

Input

[7, 5, 9, 10]

Output

1025