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)

I don't understand what the problem is. My submission gets 10/50 points. All the test examples that I am coming up with are coming out alright. Are the rest of my answers (for the submissions) wildly off, or am I just maybe missing an element (or something similar)?

Judging on your submission that got 10/50 WA...

What 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!

Thanks
I'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)?

Yeah sure! I replied to your comment on that problem page.

Again. Fun fact: the top submissions calculates the answer faster than [user]'s hardcoding submission

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.