Maximum SumGiven 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.
InputAn integer 1 < N <= 100,000.
N lines, each with one positive integer in the sequence <= 1000
OutputThe maximum sum possible.
Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 27, 2013
- Dynamic Programming
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3