Medium Divide and Conquer > Dynamic Programming

**Sanvi** is a very cute girl. She likes to play Card game very much. One day, she came with the cards with some value written in the back side of every cards. In her Card game there may be maximum of **13** and there will be at least two Cards. The Cards numbered from 1 to maximum numeric digit of available total cards. At the begin of game, Saanvi would like to make the shuffle of cards on her hand as much time as she likes so that the summation of absolute difference of every two consecutive cards from top to bottom on her hand will be maximum. Your task is to help her to find this maximum summation. Input: ------ Input starts with an integer **T (T<=1<=100)**, denoting the number of test cases. Each case contains an integer **N (2 ≤ N ≤ 13)** denoting the number of Cards in current game. The next line will contain N integers separated by spaces, **ith** of which denotes the value written on **Card number- i** . Each of these integers will be a **non negative integer upto 1000000000000**. Output: ------- For each case of input, output the maximum summation she may get after doing shuffle of cards as many times as she desires. Sample Input ------------ 2 2 1 5 3 1 3 5 Sample Output ------------- 4 6

Bishal Gautam