0

Maximum subarray

Difficulty: HARD
Avg. time to solve
55 min
Success Rate
35%

Problem Statement
Suggest Edit

Given an array of integers, find out and return the maximum sub-array of nonnegative numbers. The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth element and skipping the third element is invalid.

Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than subarray B if sum(A) > sum(B). And in case if the sum of two subarrays A & B is same, return the subarray with more number of elements.

No need to print the output subarray, you just need to return it.

Input format: `
Line 1: Size of input array`

Line 2: Array elements (separated by space)`

Constraints:

1 <= N <= 10^6
-99 <= A[i] <= 99
Sample Input :
6
1 2 5 -7 2 3
Sample Output :
1 2 5
Want to solve this problem? Login now to get access to solve the problems