View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

You are given $$N$$ cookies that are lined up in a row. Each cookie as a tastiness value, $$a_i$$. You want to maximize the sum of the tastiness values of the cookies that you eat. However, you can only eat cookies that are not adjacent to each other.

#### Input Specification

The first line will contain the integer $$N\ (1 \le N \le 100\ 000)$$.

The second line will contain $$N$$ integers, $$a_1, a_2, \ldots, a_N\ (1 \le a_i \le 10\ 000)$$.

#### Output Specification

The maximum sum of the tastiness values of the cookies you eat, satisfying the constraint that you may not eat cookies that are adjacent to one other.

$$N \le 10$$

$$N \le 1\ 000$$

No further constraints.

#### Sample Input 1

3
1 7 5

#### Sample Output 1

7

#### Explanation for Sample 1

The maximum tastiness sum would be to only take the cookie with a tastiness value of $$7$$ for a total sum of $$7$$.

#### Sample Input 2

5
1 10 4 7 8

#### Sample Output 2

18