Maximum Sum

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

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

Output

The maximum sum possible.

All Submissions
Best Solutions


Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 27, 2013

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

is the array of positive integers guaranteed to be in order from least to greatest? (eg.4 5 6 9 10 instead of 4 6 5 10 9)

The problem doesn't say this, so I don't see why you would assume it.

The question states "no two numbers in the subset may be adjacent". Adjacent as in consecutive in value or adjacent as in adjacent position in the sequence?

Adjacent in position.