Maximum Subarray Problem Statement

Ninja has been given an array, and he wants to find a subarray such that the sum of all elements in the subarray is maximum.

A subarray 'A' is considered greater than a subarray 'B' if sum(A) > sum(B). If two subarrays have the same maximum sum, choose the subarray with the larger length.

Explanation:

A subarray is a contiguous part of an array. For example, in an array arr = [1, 2, 3, 4], [1, 2], and [2, 3, 4] are contiguous subarrays, but [1, 3, 4] is not.

Input:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the array.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array.

Output:

For each case, if the returned subarray is correct then print 1, else print 0.

The output of each test case will be printed in a separate line.

Example:

Example 1:
Input: T = 1, N = 4, arr = [1, 2, -1, 3]
Output: 1
Explanation: The subarray [1, 2, -1, 3] has the maximum sum of 5.

Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 1000
• -99 ≤ |arr| ≤ 99
• Time limit: 1 sec.

Note:

You do not need to input or print anything, it has already been taken care of. Just implement the given function.