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
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
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!
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)?