A Cookie Problem

View as PDF

Submit solution

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 has 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.

Subtasks

Subtask 1 [10%]

N \le 10

Subtask 2 [30%]

N \le 1 000

Subtask 3 [60%]

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

Comments

There are no comments at the moment.