Maximum Sum

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 16M

Problem type

Given an array of (positive) integers, find a subset with the maximal sum.
However, there is the additional restriction that no two numbers in the subset may be adjacent.

For example, for the array 4, 5, 6, 9, 10: 4, 6, 10 is valid, while 5, 9, 10 is invalid since 9 and 10 are next to each other. 4, 6, 10 happens to be the optimal sum in this case, so 20 is the answer.

Input Specification

An integer 1 < N \le 100\,000.
N lines, each with one positive integer in the sequence \le 1\,000.

Output Specification

The maximum sum possible.


Comments

There are no comments at the moment.