Queation-Given an arrayarr ofNintegers. Find the contiguous sub-array with maximum sum.
Input: The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.
Output: Print the maximum sum of the contiguous sub-array in a separate line for each test case.
Constraints: 1 ≤ T ≤ 110 1 ≤ N ≤ 106 -107 ≤ A[i] <= 107