Time limit: 1.0s
Memory limit: 16M
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 :
is valid, while is invalid since and are next to each other.
happens to be the optimal sum in this case, so is the answer.
An integer .
lines, each with one positive integer in the sequence .
The maximum sum possible.