Medium Divide and Conquer > Dynamic Programming

You have **N** sticks of various length. you have to make a rectangle with maximum possible area. - You can use each stick once - You can ignore a stick if you want (not use it at all) - You can join two or more stick to make a side of rectangle. also you can use a single stick to make a side of rectangle - You **can't** break any sticks . Input: ------ First Line of input contain a integer **T (1<=T<=200)** , The number of Test case<br> Each test case start with an integer **N (4 ≤ N ≤ 15)** denoting the number of sticks. The next line will contain N positive integers separated by spaces, denoting the length of ith sticks. sum of all length will be less than or equal **30** Output: ------- Print a single integer in a line for each test case . maximum possible area of rectangle. if no rectangle is possible, print **0**. Sample Input ------------ 4 5 4 2 1 2 1 15 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 1 2 1 1 1 1 1 4 5 2 3 1 Sample Output ------------- 4 12 4 0

Md. Tariqul Islam