New update is available. Click here to update.

Maximum subarray

Posted: 26 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Ninjas has been given an array. He wants to find a subarray such that the sum of all elements in the subarray is maximum.

Subarray 'A' is greater than sub-array 'B' if sum(A) > sum(B). If two sub-array have the same maximum sum, then output the subarray that has a larger length.

A subarray means a contiguous part of an array. For example, In 'arr' = [1, 2, 3, 4], [1, 2], [2, 3, 4] are the contiguous subarry but [1, 3, 4] is not a subarray.

Note:

More than one sub-array can have a maximum sum, in that case, output any.
Input Format:
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 Format:
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.
Note:
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 1000
-99 <= |arr| <= 99

Time limit: 1 sec.