231 - Testing the Catcher
Summary of the problem statement goes here.
This problem is based in the idea of selecting a sequence of non decreasing integer elements from an array in such a way that its length is maximised.
An algorithm is fast enough for the problem to be accepted.
A dynamic programming method can be used if executed as described below:
Let be the height of the missile (i) The missile 0 is at height infinity. Let be the interception count after i missiles have been faced by the catcher. Notice that = 0.
Then can be calculated as the maximum of the elements of V indexed from 0 to i whose height is smaller than or equal to the height added of 1 (the current interception).
That way, if 5 missiles at heights 5 10 9 7 16 face the catcher, the arrays can be defined as follows:
H = infinity 5 10 9 7 16
V = 0 1 1 2 3 1
To extract the result, get the largest element of V.
--Schultz 15:32, 10 Oct 2006 (EDT)