Maximum Subarray Sum

Interview

Time limit1sMemory limit256 MB

Summary

For each test case, find the maximum sum over all contiguous subarrays of the given integer array.

Level: Easy3 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Given an integer array $X$ of size $N$ , find the maximum sum of any contiguous subarray. That is, compute $\max_{1 \le i \le j \le N} (X[i] + \cdots + X[j])$ .

Input

The first line contains the number of test cases $T$ . Each test case has one line with $N$$(1 \le N \le 1000)$ , then a line with $N$ integers separated by spaces, each with absolute value less than $1000$ .

Output

For each test case, print the maximum subarray sum on its own line.

Examples1

Example 1
Input
```
2
5
1 2 3 4 5
5
2 1 -2 3 -5
```
Expected output
```
15
4
```