Here is a variation of another popular task for practicing dynamic programming approach (though of course precise algorithm is not explained by these words).
The Rabbit is going to cross the river. There is a straight chain of tiny isles across the flow and the animal should jump from one to another because it surely could not swim.
At each of the isles there are some candies. When the Rabbit arrives to the new isle, it collects all the candies here.
However, the Rabbit could not jump directly to the next isle in the chain - it just is too strong to make short jumps.
So, instead, it can jump over the one or two isles (i.e. from the
1st for example to
4th but not
5th and further). Also the Rabbit could not jump back.
You can see the sample of the Rabbit's path on the drawing above. It visits
8th isles and
11 + 3 + 13 + 7 = 34
the amount of
34 candies. Obviously he could do better if the path is chosen more wisely.
Your task is to choose the best path for Rabbit over the given chain of isles - i.e. to maximize the amount of
the candies collected. Note that Rabbit starts from
1st isle and finishes either on the
N is the total number of isles (because from these two it will necessarily jump immediately to the other bank).
Input data will contain the number of test-cases in the first line.
Next lines contain one test-case each - i.e. one chain of isles, described by the array of numbers - amounts of candies at each isle.
Answer should contain the maximum possible amount of candies gathered for each test case.
input data: 2 11 5 3 17 2 13 19 7 9 7 12 7 16 3 7 17 14 13 4 6 11 6 3 3 5 4 11 3 15 12 14 2 15 19 11 12 answer: 48 157