Maximum Score in Card Selection

You are given a deck of cards, where each card has a positive integer value. You need to select a subset of these cards such that no two consecutive cards are chosen. In other words, if you choose a card, you must skip the next card. Your task is to determine the maximum score you can achieve by summing the values of the selected cards.

Formally, given an array of integers \(cards\) of length \(N\), define a dynamic programming array \(dp\) where:

[ \begin{aligned} &dp[0] = cards[0],\ &dp[1] = \max(cards[0], cards[1]),\ &dp[i] = \max(dp[i-1], dp[i-2] + cards[i]) \quad \text{for} \quad i \ge 2. \end{aligned} ]

The answer will be \(dp[N-1]\) if \(N > 0\), and 0 if the list is empty.

inputFormat

The input is given via standard input. The first token is an integer \(N\) representing the number of cards. This is followed by \(N\) space-separated integers, each representing the value of a card.

outputFormat

Output a single integer denoting the maximum score you can achieve by selecting cards under the given rule. The result should be printed to standard output.

1
4

4