## 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)

Chinadollon Feb 11, 2017 - 4:50:39 pm UTC ?jargonon Feb 11, 2017 - 7:17:26 pm UTC Re: ?tankibudson Sep 18, 2016 - 12:08:50 am UTC clarificationjargonon Sep 18, 2016 - 7:30:38 am UTC Re: clarificationtankibudson Sep 18, 2016 - 12:54:51 pm UTC Re: clarification