1073: pick up numbers (recursion)
[Creator : ]
Description
Given a list of integers S1,S2,S3…Sn arranged in a row. you and your friend peter take turns alternatively. In each turn the player can select either the first or the last integer in the row and remove it. The integer's value gets added to the balance. Now you need to determine how you to select the integers such that in the end you have more cash than your friend. You play first. Please note on each step, you and peter are always play with optimal solution. (That is he is as smart as you!)
Input
The first line of input contains T which is the number of test cases.
For each testcase: The first line contains a single integer N, which is the number of integers.
The second line contains N space separated integers.
constraints:
1<=T<=100
1<=N<=100
1<=Si<=1,000,000
For each testcase: The first line contains a single integer N, which is the number of integers.
The second line contains N space separated integers.
constraints:
1<=T<=100
1<=N<=100
1<=Si<=1,000,000
Output
One line for each testcase, print the amount of money you will have
Sample Input Copy
2
4
5 3 7 15
4
8 15 1 6
Sample Output Copy
20
21