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

Cameronon Jul 27, 2017 - 3:53:52 am UTC I don't understand the errorXue_Alexon Jul 30, 2017 - 1:45:45 am UTC Re: I don't understand the errorWhat about 99, 100, 99, 1, 1

Your submission would output 101, when in reality that answer would be 199 (taking 99 + 99 + 1, at indexes 0, 2, 4). I'd suggest that you look into "dynamic programming".

Also, another suggestion is that you don't name your variables something that is already in the standard library (you named a vector "set").

Good luck!

Cameronon Jul 30, 2017 - 2:34:04 pm UTC Re: I don't understand the errorI'll see about this dynamic programming solution, but I was thinking that I could simply delete elements of the vector that the solution didn't need.

Additionally, could you check my solution to Rock Climbing problem (unrelated problem)?

Xue_Alexon Aug 01, 2017 - 12:08:15 am UTC Re: I don't understand the errorgpfaulton Jul 19, 2017 - 3:16:07 am UTC [user] hardcodingChinadollon 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