Find out the maximum sub-array of non negative numbers from an array.
The sub-array should be contiguous i.e., 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 sub-array B if sum(A) > sum(B).
Example:
a = [1, 2, 5, -7, 2, 3]
The two sub-arrays are [1, 2, 5] [2, 3].
The answer is [1, 2, 5] as its sum is larger than [2, 3]
NOTE: If there is a tie, then compare with segment's length and return segment which has maximum length.
If there is still a tie, then return the segment with minimum starting index.
If no such subarray is present return "-1"
Example 1:
Input:
n = 3
a[] = {1, 2, 3}
Output: 1 2 3
Explanation: In the given array every
element is non-negative.
Example 2:
Input:
n = 2
a[] = {-1, 2}
Output: 2
Explanation: The only subarray [2] is
the answer.
 
Your Task:
Complete the function findSubarray() which takes the array a and the size of the array, n, as input parameters and returns an array representing the answer. If there is no subarray return an array of length 1 containing -1 only. You don't to print answer or take inputs.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
-10^{5 }≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Divide and conquer

Starter code: #User function Template for python3



class Solution:



	def findSubarray(self,a, n):

    	# code here

Solutions:
import numpy

class Solution:

	def findSubarray(self, a, n):
		i = 0
		maxsubarr = []
		maxsum = 0
		currentsum = 0
		for j in range(n):
			if a[j] >= 0:
				currentsum += a[j]
			if a[j] < 0 or j + 1 == n:
				if currentsum > maxsum:
					maxsum = currentsum
					if j + 1 != n:
						maxsubarr = a[i:j]
					else:
						maxsubarr = a[i:j + 1]
				elif currentsum == maxsum:
					if j - i + 1 > len(maxsubarr):
						if j + 1 != n:
							maxsubarr = a[i:j]
						else:
							maxsubarr = a[i:j + 1]
				currentsum = 0
				i = j + 1
		return maxsubarr


class Solution:

	def findSubarray(self, arr, n):
		sm = 0
		mxs = 0
		s = 0
		lst = (0, 0)
		for i in range(n):
			if arr[i] < 0:
				sm = 0
				s = i + 1
				continue
			sm += arr[i]
			if sm > mxs:
				mxs = sm
				lst = (s, i)
			elif sm == mxs:
				if i - s > lst[1] - lst[0]:
					lst = (s, i)
		ams = []
		for i in range(lst[0], lst[1] + 1):
			ams.append(arr[i])
		return ams


class Solution:

	def findSubarray(self, a, n):
		l = r = 0
		max_sum = curr_sum = 0
		max_range = [0, 0]
		while r < n:
			while r < n and a[r] > -1:
				curr_sum += a[r]
				r += 1
			else:
				if curr_sum > max_sum:
					max_sum = curr_sum
					max_range[0] = l
					max_range[1] = r
				elif curr_sum == max_sum and r - l > max_range[1] - max_range[0]:
					max_range[0] = l
					max_range[1] = r
				r += 1
				l = r
				curr_sum = 0
		return a[max_range[0]:max_range[1]]


class Solution:

	def findSubarray(self, a, n):
		id1 = 0
		id2 = 0
		i = 0
		su = 0
		mx = -1
		lis = []
		flag = True
		t = False
		while i < n:
			if a[i] < 0:
				if su > mx and t:
					mx = su
					if len(lis) > 0:
						lis.pop()
					lis.append([id1, id2])
				elif su == mx and t:
					if id2 - id1 > lis[0][1] - lis[0][0]:
						lis.pop()
						lis.append([id1, id2])
				su = 0
				flag = True
				i += 1
			else:
				t = True
				su += a[i]
				if flag:
					id1 = i
					flag = False
				id2 = i
				i += 1
				if i == n:
					if su > mx:
						if lis:
							lis.pop()
						lis.append([id1, id2])
					if su == mx:
						if id2 - id1 > lis[0][1] - lis[0][0]:
							lis.pop()
							lis.append([id1, id2])
		if len(lis) == 1:
			return a[lis[0][0]:lis[0][1] + 1]
		return -1


class Solution:

	def findSubarray(self, a, n):
		if not any((x > -1 for x in a)):
			return [-1]
		mxt = 0
		mxln = 0
		mxidx = 0
		ct = 0
		cl = 0
		ci = 0
		for i in range(n):
			if a[i] < 0 or i == n - 1:
				if i == n - 1 and a[i] > -1:
					ct += a[i]
					cl += 1
				if ct > mxt:
					mxt = ct
					mxln = cl
					mxidx = ci
				elif ct == mxt and cl > mxln:
					mxln = cl
					mxidx = ci
				ct = 0
				cl = 0
				ci = i + 1
			else:
				ct += a[i]
				cl += 1
		return a[mxidx:mxidx + mxln]


class Solution:

	def findSubarray(self, a, n):
		new_a = []
		max_a = [-1]
		max_sum = -1
		for i in range(n):
			if a[i] >= 0:
				new_a.append(a[i])
			if a[i] < 0 or i == n - 1:
				new_sum = sum(new_a)
				if new_sum > max_sum:
					max_a[:] = new_a[:]
					max_sum = new_sum
				elif new_sum < max_sum:
					pass
				elif len(new_a) > len(max_a):
					max_a[:] = new_a[:]
					max_sum = new_sum
				new_a = []
		return max_a


class Solution:

	def findSubarray(self, a, n):
		answer = []
		if max(a) < 0:
			return -1
		i = 0
		while i < n:
			l = []
			while i < n and a[i] >= 0:
				l.append(a[i])
				i = i + 1
			if len(l) != 0:
				answer.append(l)
			i = i + 1
		maxi = -1
		if len(answer) == 1:
			return answer[0]
		for y in range(len(answer)):
			if sum(answer[y]) > maxi:
				maxi = sum(answer[y])
				posi = y
			elif sum(answer[y]) == maxi:
				if len(answer[posi]) < len(answer[y]):
					posi = y
				elif len(answer[posi]) == len(answer[y]):
					if answer[posi] > answer[y]:
						posi = y
		return answer[posi]


class Solution:

	def findSubarray(self, a, n):
		sum1 = 0
		l = []
		l1 = []
		for i in range(n):
			if a[i] >= 0:
				l.append(a[i])
				if i == n - 1:
					if sum(l) == sum1 and len(l) > len(l1):
						l1 = l
					elif sum(l) > sum1:
						l1 = l
			else:
				if sum(l) == sum1 and len(l) > len(l1):
					sum1 = sum(l)
					l1 = l
				elif sum(l) > sum1:
					sum1 = sum(l)
					l1 = l
				l = []
		if len(l1) == 0:
			return [-1]
		return l1


class Solution:

	def findSubarray(self, a, n):
		curr_start = 0
		curr_max = 0
		max_start = 0
		max_end = 0
		max_sum = 0
		for i in range(n):
			if a[i] < 0:
				curr_max = 0
				curr_start = i + 1
			else:
				curr_max += a[i]
			if curr_max > max_sum:
				max_sum = curr_max
				max_start = curr_start
				max_end = i
			elif curr_max == max_sum:
				curr_diff = i - curr_start + 1
				max_diff = max_end - max_start + 1
				if curr_diff > max_diff:
					max_start = curr_start
					max_end = i
		ans = a[max_start:max_end + 1]
		if len(ans) == 0:
			return -1
		else:
			return ans


class Solution:

	def findSubarray(self, arr, n):
		max_sum = 0
		current_sum = 0
		max_len = 0
		current_len = 0
		max_start = -1
		current_start = -1
		for (i, num) in enumerate(arr):
			if num >= 0:
				if current_sum == 0:
					current_start = i
				current_sum += num
				current_len += 1
			else:
				if current_sum > max_sum:
					max_sum = current_sum
					max_len = current_len
					max_start = current_start
				elif current_sum == max_sum and current_len > max_len:
					max_len = current_len
					max_start = current_start
				current_sum = 0
				current_len = 0
		if current_sum > max_sum:
			max_sum = current_sum
			max_len = current_len
			max_start = current_start
		elif current_sum == max_sum and current_len > max_len:
			max_len = current_len
			max_start = current_start
		if max_start == -1:
			return [-1]
		else:
			return arr[max_start:max_start + max_len]


class Solution:

	def findSubarray(self, a, n):
		x = [[]]
		s = [0]
		l = [0]
		z = 0
		w = -1
		left = 0
		right = 0
		maxs = -1
		maxl = -1
		for i in range(n):
			if a[i] < 0:
				left = i + 1
				right = i + 1
				z += 1
				x.append([])
				s.append(0)
				l.append(0)
				continue
			else:
				x[z].append(a[i])
				l[z] += 1
				s[z] += a[i]
				if s[z] > maxs:
					w = z
					maxs = s[z]
					maxl = len(x[z])
				elif s[z] == maxs and l[z] > maxl:
					w = z
					maxs = s[z]
					maxl = len(x[z])
		return x[w]


class Solution:

	def findSubarray(self, a, n):
		res = []
		sum = 0
		maxsum = 0
		temparr = []
		for val in a:
			if val < 0 and temparr:
				if sum == maxsum:
					if len(temparr) > len(res):
						res = temparr
					temparr = []
					sum = 0
				elif sum > maxsum:
					res = temparr
					maxsum = sum
					temparr = []
					sum = 0
				else:
					sum = 0
					temparr = []
			elif val >= 0:
				temparr.append(val)
				sum += val
		if sum == maxsum:
			if len(temparr) > len(res):
				res = temparr
		elif sum > maxsum:
			res = temparr
		return res


class Solution:

	def findSubarray(self, a, n):
		L = []
		L1 = []
		for i in range(0, n):
			if a[i] < 0:
				L.append(L1)
				L1 = []
			else:
				L1.append(a[i])
		if L1:
			L.append(L1)
		L.sort()
		s = 0
		b = []
		for i in L:
			if sum(i) > s:
				s = sum(i)
				b = i
		if b:
			return b
		else:
			return [-1]


class Solution:

	def findSubarray(self, arr, n):
		curr_sum = 0
		curr_start = 0
		max_sum = 0
		max_start = 0
		max_end = 0
		for i in range(n):
			if arr[i] < 0:
				curr_sum = 0
				curr_start = i + 1
			else:
				curr_sum += arr[i]
			if curr_sum > max_sum:
				max_sum = curr_sum
				max_start = curr_start
				max_end = i
			elif curr_sum == max_sum:
				curr_dis = i + 1 - curr_start
				max_dis = max_end + 1 - max_start
				if curr_dis > max_dis:
					max_start = curr_start
					max_end = i + 1
		if max_end == 0:
			return [-1]
		return arr[max_start:max_end + 1]


class Solution:

	def findSubarray(self, a, n):
		maxSum = 0
		maxStart = 0
		maxEnd = 0
		currSum = 0
		currStart = 0
		for i in range(0, n):
			if a[i] < 0:
				currSum = 0
				currStart = i + 1
			else:
				currSum += a[i]
			if currSum > maxSum:
				maxSum = currSum
				maxStart = currStart
				maxEnd = i
			elif currSum == maxSum:
				currDis = i + 1 - currStart
				maxDis = maxEnd + 1 - maxStart
				if currDis > maxDis:
					maxStart = currStart
					maxEnd = i + 1
		ans = a[maxStart:maxEnd + 1]
		if len(ans) == 0:
			return -1
		else:
			return ans


class Solution:

	def findSubarray(self, a, n):
		st = end = -1
		first = last = -1
		sm = ans = 0
		lst = []
		for i in range(n + 1):
			if i < n and a[i] >= 0:
				sm += a[i]
				if st == -1:
					st = i
				end = i
			else:
				if ans < sm:
					first = st
					last = end
					ans = sm
				elif ans == sm:
					l1 = last - first
					l2 = end - st
					if l2 > l1 or first == -1:
						first = st
						last = end
				st = end = -1
				sm = 0
		if first != -1:
			for i in range(first, last + 1):
				lst.append(a[i])
		else:
			lst.append(-1)
		return lst


class Solution:

	def findSubarray(self, a, n):
		cursum = 0
		cursumarray = []
		maxsum = -1
		maxsumarray = []
		for i in range(n):
			if a[i] < 0:
				if maxsum < cursum:
					maxsum = cursum
					maxsumarray = cursumarray.copy()
				cursum = 0
				cursumarray = []
			else:
				cursum += a[i]
				cursumarray.append(a[i])
		if maxsum == cursum and len(maxsumarray) < len(cursumarray):
			maxsumarray = cursumarray.copy()
		elif maxsum < cursum:
			maxsum = cursum
			maxsumarray = cursumarray.copy()
		if maxsumarray == []:
			return [-1]
		return maxsumarray


class Solution:

	def findSubarray(self, nums, n):
		sum = s = e = 0
		temp_s = 0
		max_sum = -9999999
		for i in range(n):
			sum += nums[i]
			if nums[i] < 0:
				sum = 0
				temp_s = i + 1
			if sum > max_sum:
				max_sum = sum
				s = temp_s
				e = i
			elif sum == max_sum and e - s < i - temp_s:
				s = temp_s
				e = i
		return nums[s:e + 1]


class Solution:

	def findSubarray(self, a, n):
		(s, x, summ, msf, y) = 5 * [0]
		for i in range(0, n):
			if a[i] < 0:
				dum = msf
				msf = max(msf, summ)
				if msf == summ and i != 0 and (y - x < i - s) or msf != dum:
					x = s
					y = i - 1
				summ = 0
				s = i + 1
			else:
				summ += a[i]
		dum = msf
		msf = max(msf, summ)
		if msf == summ and i != 0 and (y - x < i - s) or msf != dum:
			x = s
			y = i
		ans = []
		p = x
		while p <= y:
			ans.append(a[p])
			p += 1
		return ans


import sys

class Solution:

	def findSubarray(self, a, n):
		msf = 0
		(s, x, summ) = 3 * [0]
		y = 0
		for i in range(0, n):
			if a[i] < 0:
				dum = msf
				msf = max(msf, summ)
				if msf == summ and i != 0 and (y - x < i - s):
					x = s
					y = i - 1
				if msf != dum:
					x = s
					y = i - 1
				summ = 0
				s = i + 1
			else:
				summ += a[i]
		dum = msf
		msf = max(msf, summ)
		if msf == summ and i != 0 and (y - x < i - s):
			x = s
			y = i
		if msf != dum:
			x = s
			y = i
		ans = []
		p = x
		while p <= y:
			ans.append(a[p])
			p += 1
		return ans


class Solution:

	def findSubarray(self, a, n):
		max_sum = -1
		cur_sum = 0
		max_range_left = -1
		max_range_right = -1
		cur_range_left = 0
		cur_range_right = 0
		while cur_range_right < n:
			if a[cur_range_right] < 0:
				cur_range_left = cur_range_right + 1
				cur_sum = 0
			else:
				cur_sum += a[cur_range_right]
				if cur_sum > max_sum:
					max_sum = cur_sum
					max_range_left = cur_range_left
					max_range_right = cur_range_right
				elif cur_sum == max_sum:
					if cur_range_right + 1 - cur_range_left > max_range_right + 1 - max_range_left:
						max_range_left = cur_range_left
						max_range_right = cur_range_right
			cur_range_right = cur_range_right + 1
		ans = []
		if max_range_left == -1 or max_range_right == -1:
			ans.append(-1)
			return ans
		for i in range(max_range_left, max_range_right + 1):
			ans.append(a[i])
		return ans


class Solution:

	def findSubarray(self, a, n):
		maxi = -10 ** 9
		res = []
		li = []
		sumi = 0
		for i in range(n):
			if a[i] >= 0:
				sumi += a[i]
				li.append(a[i])
			else:
				if sumi > maxi:
					maxi = sumi
					res = li
				elif sumi == maxi:
					if len(li) > len(res):
						res = li
				sumi = 0
				li = []
		if sumi != 0 and sumi > maxi:
			maxi = sumi
			res = li
		elif sumi != 0 and sumi == maxi:
			maxi = sumi
			if len(li) > len(res):
				res = li
		if maxi != -10 ** 9:
			return res
		return [-1]


class Solution:

	def findSubarray(self, a, n):
		fans = []
		ans = 0
		cur = []
		curSum = 0
		for i in range(n):
			if a[i] >= 0:
				curSum += a[i]
				cur.append(a[i])
			else:
				curSum = 0
				cur = []
			if curSum > ans or (curSum == ans and len(cur) > len(fans)):
				ans = curSum
				fans = cur
		return fans


class Solution:

	def findSubarray(self, a, n):
		ans = []
		x = []
		for i in range(n):
			if a[i] >= 0:
				x.append(a[i])
			else:
				if sum(ans) < sum(x):
					ans = list(x)
				if sum(ans) == sum(x):
					if len(x) > len(ans):
						ans = list(x)
				x = []
		if sum(ans) < sum(x):
			ans = list(x)
		if sum(ans) == sum(x):
			if len(x) > len(ans):
				ans = list(x)
		return ans


class Solution:

	def findSubarray(self, a, n):
		temp = []
		arr = []
		s = []
		c = []
		summ = 0
		count = 0
		for i in range(0, n):
			if a[i] >= 0:
				temp.append(a[i])
				count = count + 1
				summ = summ + a[i]
			else:
				arr.append(temp)
				temp = []
				s.append(summ)
				c.append(count)
				summ = 0
				count = 0
		arr.append(temp)
		s.append(summ)
		c.append(count)
		maxx = max(s)
		count = s.count(maxx)
		leng = -1
		if count > 1:
			for i in range(0, len(s)):
				if s[i] == maxx:
					if c[i] > leng:
						leng = c[i]
						idx = i
		else:
			idx = s.index(maxx)
		return arr[idx]


class Solution:

	def findSubarray(self, a, n):
		sum_1 = 0
		max_sum = 0
		sum_2 = 0
		lst = (0, 0)
		for i in range(n):
			if a[i] < 0:
				sum_1 = 0
				sum_2 = i + 1
				continue
			sum_1 += a[i]
			if sum_1 > max_sum:
				max_sum = sum_1
				lst = (sum_2, i)
			elif sum_1 == max_sum:
				if i - sum_2 > lst[1] - lst[0]:
					lst = (sum_2, i)
		sub_array = []
		for i in range(lst[0], lst[1] + 1):
			sub_array.append(a[i])
		return sub_array


class Solution:

	def findSubarray(self, arr, n):
		maximum = 0
		total = 0
		length = 0
		list1 = []
		for i in range(n):
			if arr[i] >= 0:
				total += arr[i]
				length += 1
			else:
				if total > maximum:
					maximum = total
					list1 = arr[i - length:i]
				elif total == maximum:
					if length > len(list1):
						list1 = arr[i - length:i]
				length = 0
				total = 0
		if length > 0:
			if total > maximum:
				list1 = arr[i - length + 1:i + 1]
			elif total == maximum and length > len(list1):
				list1 = arr[i - length + 1:i + 1]
		if list1 == []:
			return [-1]
		return list1


class Solution:

	def findSubarray(self, a, n):
		suma = 0
		maxs = 0
		s = 0
		lst = (0, 0)
		for i in range(n):
			if a[i] < 0:
				suma = 0
				s = i + 1
				continue
			suma += a[i]
			if suma > maxs:
				maxs = suma
				lst = (s, i)
			elif suma == maxs:
				if i - s > lst[1] - lst[0]:
					lst = (s, i)
		subarr = []
		for i in range(lst[0], lst[1] + 1):
			subarr.append(a[i])
		return subarr


class Solution:

	def findSubarray(self, a, n):
		summa = 0
		maxsum = 0
		suma = 0
		lst = (0, 0)
		for i in range(n):
			if a[i] < 0:
				summa = 0
				suma = i + 1
				continue
			summa += a[i]
			if summa > maxsum:
				maxsum = summa
				lst = (suma, i)
			elif summa == maxsum:
				if i - suma > lst[1] - lst[0]:
					lst = (suma, i)
		subar = []
		for i in range(lst[0], lst[1] + 1):
			subar.append(a[i])
		return subar


class Solution:

	def findSubarray(self, a, n):
		cur_sum = 0
		cur_start = -1
		max_sum = -1
		max_start = -1
		max_end = -1
		for i in range(n):
			if a[i] >= 0:
				if cur_start == -1:
					cur_start = i
				cur_sum += a[i]
				if cur_sum > max_sum or (cur_sum == max_sum and i - cur_start > max_end - max_start):
					max_sum = cur_sum
					max_start = cur_start
					max_end = i
			else:
				cur_sum = 0
				cur_start = -1
		if max_sum == -1:
			return [-1]
		else:
			return a[max_start:max_end + 1]


class Solution:

	def findSubarray(self, a, n):
		sum = 0
		m = -10 ** 8
		l = []
		(i, j) = (0, 0)
		while j < n:
			if a[j] < 0:
				if l == []:
					l = [sum, i, j]
				elif sum == l[0] and j - i > l[2] - l[1]:
					l = [sum, i, j]
				elif sum > l[0]:
					l = [sum, i, j]
				j += 1
				i = j
				sum = 0
			else:
				sum += a[j]
				j += 1
		if l == []:
			l = [sum, i, j]
		elif sum == l[0] and j - i > l[2] - l[1]:
			l = [sum, i, j]
		elif sum > l[0]:
			l = [sum, i, j]
		res = []
		for x in range(l[1], l[2]):
			res.append(a[x])
		return res


class Solution:

	def findSubarray(self, a, n):
		d = {}
		i = 0
		j = 0
		while j < n:
			while j < n and a[j] >= 0:
				j += 1
			summa = sum(a[i:j])
			if not summa in d or j - i > len(d[summa]):
				d[summa] = a[i:j]
			while j < n and a[j] < 0:
				j += 1
			i = j
		return d[max(d.keys())]


class Solution:

	def findSubarray(self, a, n):
		if not a:
			return [-1]
		cur = 0
		mxs = 0
		s = 0
		lst = (0, 0)
		for i in range(n):
			if a[i] < 0:
				cur = 0
				s = i + 1
				continue
			cur += a[i]
			if cur > mxs:
				mxs = cur
				lst = (s, i)
			elif cur == mxs:
				if i - s > lst[1] - lst[0]:
					lst = (s, i)
		ans = []
		for i in range(lst[0], lst[1] + 1):
			ans.append(a[i])
		return ans


class Solution:

	def check(self, ts, cs, a, p1, p2, ans):
		if cs > ts:
			return a[p1:p2]
		elif cs == ts:
			k = len(a[p1:p2])
			t = len(ans)
			if t > 0 and k > t:
				return a[p1:p2]
			elif t > 0 and k == t:
				if a[p1] < ans[0]:
					return a[p1:p2]
				else:
					return ans
		return ans

	def findSubarray(self, a, n):
		(p1, p2, cs, ts) = (0, 0, 0, -2147483678)
		ans = []
		while p1 < len(a):
			if p2 == len(a):
				ans = self.check(ts, cs, a, p1, p2, ans)
				p1 = p2
				if len(ans) == 0:
					ans.append(-1)
				return ans
			if a[p2] < 0:
				ans = self.check(ts, cs, a, p1, p2, ans)
				ts = max(ts, sum(ans))
				p1 = p2 + 1
				p2 += 1
				cs = 0
			else:
				cs = cs + a[p2]
				p2 += 1
		return ans


class Solution:

	def findSubarray(self, a, n):
		lis = []
		c = 0
		mx = 0
		sm = 0
		mxint = [-1, -1]
		for i in range(n):
			if a[i] < 0:
				c = 0
				sm = 0
			else:
				c += 1
				sm += a[i]
			if mx == sm and c > mxint[0]:
				mxint = [c, i + 1]
			if mx < sm:
				mx = sm
				mxint = [c, i + 1]
		return a[mxint[1] - mxint[0]:mxint[1]]


class Solution:

	def findSubarray(self, A, N):
		l = csum = 0
		cmax = -1
		ans = [-1]
		for i in range(N):
			if A[i] < 0:
				csum = 0
				l = i + 1
				continue
			csum += A[i]
			if csum > cmax:
				cmax = csum
				ans = (l, i)
			elif csum == cmax and ans[1] - ans[0] < i - l:
				ans = (l, i)
		if len(ans) == 1:
			return ans
		return A[ans[0]:ans[1] + 1]


class Solution:

	def findSubarray(self, a, n):
		Max = -1
		Sum = 0
		res = []
		l = 0
		Max = -1
		ar = [-1]
		for i in range(n):
			if a[i] >= 0:
				Sum += a[i]
				l += 1
				res.append(a[i])
			else:
				if Sum == Max:
					if len(res) > len(ar):
						ar = res
				elif Sum > Max:
					Max = Sum
					ar = res
				Sum = 0
				res = []
		if Sum == Max:
			if len(res) > len(ar):
				ar = res
		elif Sum > Max:
			ar = res
		return ar


class Solution:

	def findSubarray(self, arr, n):
		finalStart = finalEnd = 0
		finalSum = finalWindowSize = 0
		start = currentSum = currentWindowSize = 0
		for i in range(n):
			if arr[i] < 0:
				currentSum = 0
				start = i + 1
				continue
			currentSum += arr[i]
			end = i
			currentWindowSize = end - start + 1
			if currentSum > finalSum:
				finalStart = start
				finalEnd = end
				finalSum = currentSum
				finalWindowSize = currentWindowSize
			elif currentSum == finalSum:
				if currentWindowSize > finalWindowSize:
					finalStart = start
					finalEnd = end
					finalWindowSize = currentWindowSize
		if finalWindowSize == 0:
			return '-1'
		return arr[finalStart:finalEnd + 1]


class Solution:

	def findSubarray(self, A, n):
		subArrays = []
		temp = []
		for i in range(n):
			if i == n - 1 and A[i] > 0:
				temp.append(A[i])
				x = temp.copy()
				subArrays.append(x)
			elif A[i] < 0:
				x = temp.copy()
				if len(x) != 0:
					subArrays.append(x)
				temp.clear()
			else:
				temp.append(A[i])
		if len(subArrays) == 0:
			return [-1]
		subArrayLength = len(subArrays)
		maxArr = []
		for i in range(subArrayLength):
			if i != subArrayLength - 1:
				firstArrSum = sum(subArrays[i])
				secondArrSum = sum(subArrays[i + 1])
				if firstArrSum > secondArrSum and firstArrSum > sum(maxArr):
					maxArr = subArrays[i]
				elif secondArrSum > firstArrSum and secondArrSum > sum(maxArr):
					maxArr = subArrays[i + 1]
				elif firstArrSum == secondArrSum and firstArrSum > sum(maxArr):
					if len(subArrays[i]) > len(subArrays[i + 1]):
						maxArr = subArrays[i]
					elif len(subArrays[i + 1]) > len(subArrays[i]):
						maxArr = subArrays[i + 1]
					else:
						indexOfFirstArr = A.index(subArrays[i][0])
						indexOfSecondArr = A.index(subArrays[i + 1][0])
						if indexOfFirstArr < indexOfSecondArr:
							maxArr = subArrays[i]
						elif indexOfFirstArr > indexOfSecondArr:
							maxArr = subArrays[i + 1]
						else:
							return [-1]
			elif i == subArrayLength - 1 and len(maxArr) == 0:
				maxArr = subArrays[i]
			elif i == subArrayLength - 1:
				if sum(subArrays[i]) > sum(maxArr):
					maxArr = subArrays[i]
		return maxArr


class Solution:

	def findSubarray(self, a, n):
		i = -1
		j = 0
		s = 0
		curs = 0
		first = -1
		last = -1
		while j < n:
			if a[j] >= 0:
				if i < 0:
					i = j
				curs += a[j]
				j += 1
			else:
				if curs > s:
					s = curs
					first = i
					last = j
				elif curs == s:
					if last - first < j - i:
						s = curs
						first = i
						last = j
				i = -1
				j += 1
				curs = 0
		if curs > s:
			s = curs
			first = i
			last = j
		elif curs == s:
			if last - first < j - i:
				s = curs
				first = i
				last = j
		if first == -1:
			return [-1]
		return a[first:last]


class Solution:

	def findSubarray(self, a, n):
		max_till_now = -10000
		max_now = 0
		s = 0
		end = 0
		start = 0
		for i in range(n):
			if a[i] >= 0:
				max_now += a[i]
				if max_now == max_till_now:
					if end - start < i - s:
						max_till_now = max_now
						start = s
						end = i
				if max_now > max_till_now:
					max_till_now = max_now
					end = i
					start = s
				if max_now < 0:
					max_now = 0
					s = i + 1
			else:
				max_now = 0
				s = i + 1
		result = [a[i] for i in range(start, end + 1)]
		if len(result) == 0:
			return -1
		else:
			return result


class Solution:

	def findSubarray(self, a, n):
		ms = 0
		cs = 0
		t = []
		arr = []
		for i in range(n):
			if a[i] >= 0:
				cs += a[i]
				t.append(a[i])
			else:
				if ms <= cs:
					ms = cs
					arr = []
					arr.extend(t)
				cs = 0
				t = []
		if cs >= ms and len(t) > len(arr):
			return t
		return arr


class Solution:

	def findSubarray(self, a, n):
		su = 0
		i = 0
		start = 0
		end = -1
		start_ind = {}
		end_ind = {}
		while i < n:
			if a[i] >= 0:
				end = i
				su += a[i]
			if a[i] < 0:
				if su in start_ind:
					if end - start > end_ind[su] - start_ind[su]:
						start_ind[su] = start
						end_ind[su] = end
				else:
					start_ind[su] = start
					end_ind[su] = end
				start = i + 1
				su = 0
			i += 1
		if su in start_ind:
			if end - start > end_ind[su] - start_ind[su]:
				start_ind[su] = start
				end_ind[su] = end
		else:
			start_ind[su] = start
			end_ind[su] = end
		return a[start_ind[max(start_ind)]:end_ind[max(start_ind)] + 1]


class Solution:

	def findSubarray(self, arr, n):
		sum = 0
		max_length = 0
		max_sum = 0
		index1 = 0
		index2 = 0
		curr = 0
		prev = 0
		unfav = 0
		while curr < n and prev < n:
			if arr[curr] >= 0:
				sum += arr[curr]
				if sum > max_sum:
					max_sum = sum
					max_length = curr + 1 - prev
					index1 = prev
					index2 = curr
					unfav = 0
				elif sum == max_sum and max_length < curr + 1 - prev:
					max_length = curr + 1 - prev
					index1 = prev
					index2 = curr
					unfav = 0
				curr += 1
			else:
				sum = 0
				curr += 1
				prev = curr
		result = []
		for i in range(index1, index2 + 1):
			result.append(arr[i])
		return result or [-1]


class Solution:

	def findSubarray(self, a, n):
		start = 0
		end = 0
		msum = 0
		maxi = end - start + 1
		curs = 0
		cure = 0
		sum = 0
		for i in range(n):
			if a[i] < 0:
				curs = i + 1
				sum = 0
				continue
			cur = sum + a[i]
			sum = cur
			if cur > msum:
				cure = i
				msum = cur
				end = i
				start = curs
			elif cur == msum:
				cure = i
				if cure - curs + 1 > end - start + 1:
					end = cure
					start = curs
		return a[start:end + 1]


class Solution:

	def findSubarray(self, arr, n):
		max_so_far = 0
		max_right_here = 0
		start = 0
		end = 0
		s = 0
		for i in range(0, n):
			if arr[i] < 0:
				s = i + 1
				max_right_here = 0
			else:
				max_right_here += arr[i]
			if max_right_here > max_so_far or (max_right_here == max_so_far and i - s > end - start):
				max_so_far = max_right_here
				start = s
				end = i
		return arr[start:end + 1]


class Solution:

	def findSubarray(self, a, n):
		curr = 0
		maxi = 0
		start = 0
		end = 0
		f = 0
		i = 0
		while i < n:
			if a[i] >= 0:
				f = 1
				start = i
				sm = 0
				while i < n and a[i] >= 0:
					sm += a[i]
					i += 1
					end = i
				if sm > maxi:
					maxi = sm
					ans = [start, end]
				elif sm == maxi and end - start > ans[1] - ans[0]:
					ans = [start, end]
			else:
				i += 1
		if f == 0:
			return [-1]
		return a[ans[0]:ans[1]]


class Solution:

	def findSubarray(self, arr, n):
		cs = 0
		ma = float('-inf')
		first = -1
		last = 0
		(max_first, max_last) = (float('-inf'), float('-inf'))
		for (i, a) in enumerate(arr):
			if a < 0:
				cs = 0
				first = -1
				last = 0
				continue
			cs += a
			if first == -1:
				first = i
			last = i + 1
			if cs >= ma:
				if cs > ma:
					ma = cs
					(max_first, max_last) = (first, last)
				elif last - first > max_last - max_first:
					(max_first, max_last) = (first, last)
		if max_first == float('-inf'):
			return [-1]
		return arr[max_first:max_last]


class Solution:

	def findSubarray(self, a, n):
		a.append(-1)
		(s, e, sum, maxi, cou, maxCou) = (0, 0, 0, -1, 0, 0)
		for i in range(n + 1):
			if a[i] >= 0:
				sum += a[i]
				cou += 1
			else:
				if sum > maxi:
					e = i
					s = e - cou
					maxCou = cou
					maxi = sum
				elif sum == maxi and cou > maxCou:
					e = i
					s = e - cou
					maxCou = cou
					maxi = sum
				sum = 0
				cou = 0
		return a[s:e]


class Solution:

	def findSubarray(self, a, n):
		maxi = 0
		op = []
		t = []
		s = 0
		for i in range(n):
			if a[i] >= 0:
				s += a[i]
				t.append(a[i])
			else:
				if maxi < s:
					op = t.copy()
					maxi = s
					t = []
				elif maxi == s:
					if len(op) < len(t):
						op = t.copy()
				t = []
				s = 0
		if maxi < s:
			op = t.copy()
		elif maxi == s:
			if len(op) < len(t):
				op = t.copy()
		if len(op) > 0:
			return op
		return [-1]


class Solution:

	def findSubarray(self, arr, n):
		sm = 0
		mxs = 0
		s = 0
		res = (0, 0)
		for i in range(n):
			if arr[i] < 0:
				sm = 0
				s = i + 1
				continue
			sm += arr[i]
			if sm > mxs:
				mxs = sm
				res = (s, i)
			elif sm == mxs:
				if i - s > res[1] - res[0]:
					res = (s, i)
		ans = []
		for i in range(res[0], res[1] + 1):
			ans.append(arr[i])
		return ans


class Solution:

	def findSubarray(self, a, n):
		cursum = 0
		maxsum = 0
		start = -1
		end = -1
		ind = []
		for i in range(n):
			if start == -1:
				(start, end) = (i, i)
			if a[i] < 0:
				ind.append([cursum, start, end])
				start = -1
				end = -1
				cursum = 0
			elif a[i] > 0:
				cursum += a[i]
			end = i
		if start != -1:
			ind.append([cursum, start, end])
		res = -1
		m = len(ind)
		for i in range(m):
			if ind[i][0] > maxsum:
				maxsum = ind[i][0]
				res = i
			elif ind[i][0] == maxsum and res != -1 and (ind[i][2] - ind[i][1] > ind[res][2] - ind[res][1]):
				res = i
		if res == -1:
			return -1
		ans = []
		a1 = ind[res][1]
		a2 = ind[res][2]
		for i in range(a1, a2 + 1):
			ans.append(a[i])
		return ans


class Solution:

	def findSubarray(self, a, n):
		summ = 0
		tempsum = 0
		tem_arr = []
		arr = []
		for i in range(n):
			if a[i] >= 0:
				tempsum += a[i]
				tem_arr.append(a[i])
			else:
				if tempsum >= summ:
					summ = tempsum
					arr = []
					arr.extend(tem_arr)
				tempsum = 0
				tem_arr = []
		if tempsum >= summ and len(tem_arr) > len(arr):
			return tem_arr
		else:
			return arr


class Solution:

	def findSubarray(self, a, n):
		max_sum = None
		start = end = None
		cur_sum = 0
		i = j = 0
		for v in a:
			if v >= 0:
				j += 1
				cur_sum += v
			if v < 0 or j >= n:
				if not max_sum or (cur_sum > max_sum or (cur_sum == max_sum and j - i > end - start)):
					max_sum = cur_sum
					start = i
					end = j
				i = j = j + 1
				cur_sum = 0
		if max_sum:
			return a[start:end]
		return [-1]


class Solution:

	def findSubarray(self, a, n):
		currArr = []
		currSum = 0
		maximumSum = 0
		ansArr = []
		for i in range(n):
			if a[i] < 0:
				if currSum > maximumSum:
					maximumSum = currSum
					ansArr = currArr
				elif currSum == maximumSum:
					if len(ansArr) < len(currArr):
						ansArr = currArr
				currSum = 0
				currArr = []
			else:
				currSum += a[i]
				currArr.append(a[i])
		if currSum == 0 and maximumSum == 0:
			return [-1]
		if currSum > maximumSum:
			ansArr = currArr
		elif currSum == maximumSum:
			if len(ansArr) < len(currArr):
				ansArr = currArr
		return ansArr


from itertools import groupby

class Solution:

	def findSubarray(self, a, n):
		(res, ans) = ([-1], 0)
		func = lambda x: x >= 0
		arr = [list(group) for (k, group) in groupby(a, func) if k]
		for l in arr:
			sm = sum(l)
			if sm > ans:
				ans = sm
				res = l
			elif sm == ans and len(l) > len(res):
				ans = sm
				res = l
		return res


from itertools import groupby

class Solution:

	def findSubarray(self, a, n):
		(sub, sum_, length, index) = ([], [], [], [])
		sub = [list(g) for (k, g) in groupby(a, key=lambda x: x >= 0) if k == True]
		if not any(sub):
			return [-1]
		sum_ = list(map(sum, sub))
		max_sum = tuple([k for (k, j) in enumerate(sum_) if j == max(sum_)])
		if len(max_sum) == 1:
			return sub[max_sum[0]]
		sub = [sub[i] for i in max_sum]
		length = list(map(len, sub))
		max_length = tuple([k for (k, j) in enumerate(length) if j == max(length)])
		if len(max_length) == 1:
			return sub[max_length[0]]
		else:
			sub_biggest = [sub[i, 0] for i in max_length]
			index = list(map(len, sub_biggest))
			min_index = [k for (k, j) in enumerate(index) if j == min(index)]
			return sub[max_sum[min_index[0]]]


class Solution:

	def findSubarray(self, a, n):
		start = 0
		stop = -1
		(i, j, mx, sm) = (0, 0, 0, 0)
		while j < n:
			if a[j] >= 0:
				sm += a[j]
				j += 1
			else:
				if mx < sm:
					mx = sm
					start = i
					stop = j - 1
				sm = 0
				j += 1
				i = j
		if mx < sm:
			mx = sm
			start = i
			stop = j - 1
		res = []
		for i in range(start, stop + 1):
			res.append(a[i])
		if len(res) == 0:
			res.append(-1)
		return res


class Solution:

	def findSubarray(self, a, n):
		i = j = currSum = mx = 0
		start = end = -1
		while j < n:
			if a[j] < 0:
				if currSum > mx or (currSum == mx and j - i > end - start):
					mx = currSum
					start = i
					end = j
				i = j + 1
				currSum = 0
			else:
				currSum += a[j]
			j += 1
		if currSum > mx or (currSum == mx and j - i > end - start):
			start = i
			end = j
		if start != -1:
			return [a[i] for i in range(start, end)]
		return [-1]