Maximum Value Without Consecutive Picks

You are given a list of n non-negative integers. Each integer represents the value of an item. You must choose a subset of these items such that no two consecutive items are selected. Your task is to maximize the total value collected.

You can solve this problem using dynamic programming. Let \(dp[i]\) be the maximum value using items from index 0 to \(i\). The recurrence relation is given by:

\(dp[i] = \max(dp[i-1], dp[i-2] + \text{values}[i])\) for \(i \geq 2\).

Consider the following examples:

• For n = 6 and values = [4, 1, 5, 8, 3, 7], the maximum value is 19.
• For n = 4 and values = [5, 3, 4, 11], the maximum value is 16.

inputFormat

The input is read from stdin and consists of two lines.

• The first line contains a single integer n, the number of items.
• The second line contains n space-separated integers representing the values of the items.

outputFormat

Output a single integer to stdout which represents the maximum value that can be obtained without picking two consecutive items.

6
4 1 5 8 3 7

19