Maximum Contiguous Subarray Sum

Problem Statement

Given an array of integers, your task is to find the maximum sum of any contiguous subarray. Formally, if the array is \(a_1, a_2, \dots, a_n\), you need to compute:

\(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\)

This problem is a classic example that can be solved efficiently using Kadane's algorithm.

Consider both positive and negative integers in the array. Even if all numbers are negative, the maximum subarray sum is the largest (i.e., least negative) number.

inputFormat

Input Format

The first line of input contains a single integer \(T\) denoting the number of test cases.

Each test case consists of two lines:

• The first line contains an integer \(N\), the number of elements in the array.
• The second line contains \(N\) space-separated integers representing the array elements.

outputFormat

Output Format

For each test case, output a single line containing one integer — the maximum sum of any contiguous subarray.

## sample

2
3
-2 1 -3
5
1 2 -1 2 3

1
7

</p>