Given an array of integers, check whether there is a subsequence with odd sum and if yes, then finding the maximum odd sum. If no subsequence contains odd sum, print -1.
Example 1:
Input:
N=4
arr[] = {4, -3, 3, -5}
Output: 7
Explanation:
The subsequence with maximum odd
sum is 4 + 3 = 7
Example 2:
Input:
N=5
arr[] = {2, 5, -4, 3, -1}
Output: 9
Explanation:
The subsequence with maximum odd 
sum is 2 + 5 + 3 + -1 = 9
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function findMaxOddSubarraySum() that takes array arr and integer N as parameters and returns the desired value.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
2 ≤ N ≤ 10^{7}
-10^{3} <= arr[i] <= 10^{3}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3


class Solution:
    def findMaxOddSubarraySum(self,arr,n):
        #code here.



Solutions:
class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		s = 0
		mn = 99999
		for i in range(n):
			if arr[i] > 0:
				s += arr[i]
			if arr[i] % 2 != 0:
				mn = min(mn, abs(arr[i]))
		if s % 2 != 0:
			return s
		elif mn == 99999:
			return -1
		else:
			return s - mn


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		odd = 9999999
		a = 0
		for i in range(n):
			if arr[i] > 0:
				a += arr[i]
			if arr[i] % 2 != 0:
				odd = min(odd, abs(arr[i]))
		if a % 2 != 0:
			return a
		elif odd == 9999999:
			return -1
		else:
			return a - odd


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		(min_odd_pos, pos, max_odd_neg) = (float('inf'), 0, float('-inf'))
		for elem in arr:
			if elem % 2 == 1 and elem > 0 and (elem < min_odd_pos):
				min_odd_pos = elem
			if elem > 0:
				pos += elem
			elif elem % 2 == 1 and elem > max_odd_neg:
				max_odd_neg = elem
		if max_odd_neg == float('-inf') and min_odd_pos == float('inf'):
			return -1
		elif max_odd_neg == float('-inf') or min_odd_pos <= abs(max_odd_neg):
			sub = min_odd_pos
		elif min_odd_pos > abs(max_odd_neg):
			sub = abs(max_odd_neg)
		return pos if pos % 2 == 1 else pos - sub


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		minodd = 100000000.0
		s = 0
		isodd = False
		for i in range(n):
			if arr[i] > 0:
				s += arr[i]
			if arr[i] % 2 != 0:
				isodd = True
				minodd = min(minodd, abs(arr[i]))
		if isodd == False:
			return -1
		if s % 2 != 0:
			return s
		return s - minodd


import math

class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		min_odd = math.inf
		alleven = True
		s = 0
		for i in range(n):
			if arr[i] > 0:
				s = s + arr[i]
			if arr[i] % 2 != 0:
				alleven = False
				min_odd = min(min_odd, abs(arr[i]))
		if alleven:
			return -1
		if s % 2 == 0:
			s = s - min_odd
		return s


import math

class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		min_odd = math.inf
		isOdd = False
		sum = 0
		for i in range(n):
			if arr[i] > 0:
				sum = sum + arr[i]
			if arr[i] % 2 != 0:
				isOdd = True
				if min_odd > abs(arr[i]):
					min_odd = abs(arr[i])
		if isOdd == False:
			return -1
		if sum % 2 == 0:
			sum = sum - min_odd
		return sum


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		sum = 0
		a1 = []
		for i in range(n):
			if arr[i] > 0:
				sum += arr[i]
				if arr[i] % 2 != 0:
					a1.append(arr[i])
			elif arr[i] < 0 and arr[i] % 2 != 0:
				a1.append(abs(arr[i]))
		if sum % 2 != 0:
			return sum
		elif len(a1) != 0:
			return sum - abs(min(a1))
		return -1


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		possible = False
		odd_heap = []
		min_odd = 1001
		for item in arr:
			if item % 2 != 0:
				possible = True
				break
		if not possible:
			return -1
		pos_sum = 0
		for item in arr:
			if item > 0:
				pos_sum += item
			if item % 2 != 0:
				min_odd = min(abs(item), min_odd)
		if pos_sum % 2 != 0:
			return pos_sum
		else:
			return pos_sum - min_odd


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		min_odd = 100000
		isodd = False
		s = 0
		for i in arr:
			if i > 0:
				s += i
			if i % 2 != 0:
				isodd = True
				if min_odd > abs(i):
					min_odd = abs(i)
		if not isodd:
			return -1
		if s % 2 != 0:
			return s
		return s - min_odd


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		min_odd = None
		sum_arr = 0
		odd = 0
		for i in arr:
			if abs(i) % 2 == 1:
				odd = i
				if min_odd == None:
					min_odd = abs(i)
				else:
					min_odd = min(abs(i), min_odd)
			if i > 0:
				sum_arr += i
		if odd == 0:
			return -1
		if sum_arr % 2 == 1:
			return sum_arr
		else:
			return sum_arr - abs(min_odd)


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		o = 0
		for j in arr:
			if j > 0:
				o += j
		m = o
		if o % 2 == 1:
			return o
		else:
			f = 0
			s = -10 ** 3 - 1
			for j in arr:
				if m - abs(j * 1) > s and (m - abs(j)) % 2 == 1:
					s = m - abs(j)
			if s == -10 ** 3 - 1:
				return -1
			return s
		return -1


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		flag = True
		mxsum = 0
		minabsval = 99999
		for i in range(n):
			if arr[i] > 0:
				mxsum += arr[i]
			if arr[i] % 2 != 0:
				flag = False
				if abs(arr[i]) < minabsval:
					minabsval = abs(arr[i])
		if flag == True:
			return -1
		if mxsum % 2 == 0:
			mxsum -= minabsval
		return mxsum


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		flag = True
		maxSum = 0
		minAbsVal = 999999999999999999
		for i in range(n):
			if arr[i] > 0:
				maxSum += arr[i]
			if arr[i] % 2 != 0:
				flag = False
				if abs(arr[i]) < minAbsVal:
					minAbsVal = abs(arr[i])
		if flag == True:
			return -1
		if maxSum % 2 == 0:
			maxSum -= minAbsVal
		return maxSum


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		summa = 0
		extra = float('inf')
		check = False
		for item in arr:
			if item > 0:
				summa += item
			if item % 2 and abs(item) < extra:
				extra = abs(item)
				check = True
		return summa if summa % 2 else summa - extra if check else -1


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		min_odd = +2147483647
		isOdd = False
		sum = 0
		for i in range(n):
			if arr[i] > 0:
				sum = sum + arr[i]
			if arr[i] % 2 != 0:
				isOdd = True
				if min_odd > abs(arr[i]):
					min_odd = abs(arr[i])
		if isOdd == False:
			return -1
		if sum % 2 == 0:
			sum = sum - min_odd
		return sum


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		isOdd = False
		tot = 0
		minOdd = float('inf')
		for val in arr:
			if val > 0:
				tot += val
			if val % 2 != 0:
				isOdd = True
				if minOdd > abs(val):
					minOdd = abs(val)
		if tot % 2 == 0:
			tot -= minOdd
		return tot if isOdd else -1


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		boi = False
		for i in range(n):
			if arr[i] % 2 == 0:
				boi = True
			if arr[i] % 2 != 0:
				boi = False
				break
		if boi:
			return -1
		else:
			s = 0
			for x in arr:
				if x > 0:
					s += x
			if s % 2 != 0:
				return s
			else:
				maxvalue = -1000000000.0
				for x in arr:
					if x % 2 != 0:
						value = -abs(x)
						if value > maxvalue:
							maxvalue = value
				return s + maxvalue


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		sum = 0
		mi = 9999
		for i in range(n):
			if arr[i] > 0:
				sum += arr[i]
			if arr[i] % 2 != 0:
				if mi > abs(arr[i]):
					mi = abs(arr[i])
		if mi == 9999:
			return -1
		elif sum % 2 == 0:
			return sum - mi
		else:
			return sum


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		minodd = 2e+31
		isodd = False
		s = 0
		for i in range(n):
			if arr[i] > 0:
				s += arr[i]
			if arr[i] % 2 != 0:
				isodd = True
				if minodd > abs(arr[i]):
					minodd = abs(arr[i])
		if not isodd:
			return -1
		if s % 2 == 0:
			s -= minodd
		return s


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		min_odd = float('inf')
		currSum = 0
		for i in range(len(arr)):
			if arr[i] > 0:
				currSum += arr[i]
			if arr[i] % 2 != 0:
				min_odd = min(min_odd, abs(arr[i]))
		if min_odd != float('inf'):
			if currSum % 2 == 0:
				return currSum - min_odd
			return currSum
		return -1


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		isodd = False
		mno = 99999
		mxo = 0
		for i in arr:
			if i > 0:
				mxo += i
			if i % 2 != 0:
				isodd = True
				mno = min(mno, abs(i))
		if isodd == False:
			return -1
		if mxo % 2 == 0:
			return mxo - mno
		else:
			return mxo


import sys

class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		minodd = sys.maxsize
		s = 0
		isodd = False
		for x in arr:
			if x > 0:
				s += x
			if x % 2 != 0:
				isodd = True
				minodd = min(minodd, abs(x))
		if s % 2 == 0:
			s = s - minodd
		if isodd == False:
			return -1
		else:
			return s


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		max_odd = 0
		min_odd = 99999999
		isodd = False
		for i in arr:
			if i > 0:
				max_odd += i
			if i % 2 != 0:
				isodd = True
				if min_odd > abs(i):
					min_odd = abs(i)
		if isodd == False:
			return -1
		if max_odd % 2 == 0:
			return max_odd - min_odd
		return max_odd


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		isodd = False
		sum = 0
		mim = 100000.0
		for i in range(n):
			if arr[i] > 0:
				sum += arr[i]
			if arr[i] % 2 != 0:
				isodd = True
				if mim > abs(arr[i]):
					mim = abs(arr[i])
		if isodd == False:
			return -1
		if sum % 2 == 0:
			sum -= mim
		return sum


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		s = 0
		od = 999999999
		f = 0
		for i in arr:
			if i > 0:
				s += i
			if i % 2 != 0:
				f = 1
				if abs(i) < od:
					od = abs(i)
		if f == 0:
			return -1
		if s % 2 == 0:
			return s - od
		return s


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		min_odd = 99999
		pos_sum = 0
		isOdd = False
		for i in range(n):
			if arr[i] > 0:
				pos_sum += arr[i]
			if arr[i] % 2 == 1:
				isOdd = True
				if min_odd > abs(arr[i]):
					min_odd = abs(arr[i])
		if isOdd == False:
			return -1
		if pos_sum % 2 == 0:
			return pos_sum - min_odd
		return pos_sum


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		s = 0
		for i in range(len(arr)):
			if arr[i] > 0:
				s += arr[i]
			else:
				arr[i] = -arr[i]
		f = 0
		m = max(arr)
		for i in arr:
			if i % 2 == 1:
				f = 1
				if i < m:
					m = i
		if f == 0:
			return -1
		if s % 2 == 1:
			return s
		else:
			return s - m
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	ans = ob.findMaxOddSubarraySum(a, n)
	print(ans)


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		flag = True
		maxx = 0
		minAbsValue = float('inf')
		for i in range(n):
			if arr[i] > 0:
				maxx += arr[i]
			if arr[i] % 2 != 0:
				flag = False
				if abs(arr[i]) < minAbsValue:
					minAbsValue = abs(arr[i])
		if flag == True:
			return -1
		if maxx % 2 == 0:
			maxx -= minAbsValue
		return maxx
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	ans = ob.findMaxOddSubarraySum(a, n)
	print(ans)


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		s = 0
		b = []
		for i in range(n):
			if arr[i] < 0:
				b.append(abs(arr[i]))
			else:
				s = s + arr[i]
				b.append(arr[i])
		b.sort()
		if s % 2 == 1:
			return s
		else:
			for i in b:
				if i % 2 == 1:
					return s - i
		return -1
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	ans = ob.findMaxOddSubarraySum(a, n)
	print(ans)


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		sumx = 0
		ans = -1
		isodd = False
		minx = float('inf')
		for i in range(n):
			if arr[i] > 0:
				sumx += arr[i]
			if arr[i] % 2 != 0:
				isodd = True
				if abs(arr[i]) < minx:
					minx = abs(arr[i])
		if not isodd:
			return ans
		ans = sumx
		if sumx % 2 == 0:
			ans = sumx - minx
		return ans


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		minpo = None
		posum = 0
		for i in arr:
			if i > 0:
				posum += i
			if i % 2 == 1:
				if minpo == None:
					minpo = abs(i)
				if abs(i) < minpo:
					minpo = abs(i)
		if minpo:
			if posum % 2 == 1:
				return posum
			return posum - minpo
		return -1


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		flag = True
		maxsum = 0
		minabs = float('inf')
		for i in range(0, n):
			if a[i] > 0:
				maxsum += a[i]
			if a[i] % 2 != 0:
				flag = False
				if abs(a[i]) < minabs:
					minabs = abs(a[i])
		if flag == True:
			return -1
		if maxsum % 2 == 0:
			maxsum -= minabs
		return maxsum


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		isOdd = False
		msum = 0
		minOdd = 10 ** 9 + 7
		for i in arr:
			if i > 0:
				msum += i
			if i % 2 != 0:
				isOdd = True
				if minOdd > abs(i):
					minOdd = abs(i)
		if isOdd == False:
			return -1
		if msum % 2 == 0:
			msum -= minOdd
		return msum


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		Arr = sorted(arr)
		A = []
		Sum = 0
		krr = []
		for i in range(0, len(Arr)):
			if Arr[i] < 0:
				krr.append(abs(Arr[i]))
			elif Arr[i] == 0:
				continue
			else:
				Sum += Arr[i]
				krr.append(abs(Arr[i]))
		krr.sort()
		if Sum % 2 != 0:
			return Sum
		else:
			for i in krr:
				if i % 2 != 0:
					return Sum - i
		return -1


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		s = 0
		for i in range(len(arr)):
			if arr[i] > 0:
				s += arr[i]
			else:
				arr[i] = -arr[i]
		f = 0
		m = max(arr)
		for i in arr:
			if i % 2 == 1:
				f = 1
				if i < m:
					m = i
		if f == 0:
			return -1
		if s % 2 == 1:
			return s
		else:
			return s - m


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		sp = 0
		flag = 0
		l = []
		for i in arr:
			if i % 2 != 0:
				flag = 1
				break
		if flag == 0:
			return -1
		for i in arr:
			if i > 0:
				sp += i
			l.append(abs(i))
		if sp % 2 != 0:
			return sp
		l.sort()
		for i in l:
			if i > 0 and i % 2 != 0:
				return sp - i


class Solution:

	def findMaxOddSubarraySum(self, arr, n):
		sumPos = 0
		smallestPosOdd = 0
		largestNegOdd = 0
		for i in range(0, n):
			if arr[i] > 0:
				sumPos += arr[i]
			if arr[i] % 2 == 1:
				if arr[i] > 0:
					if smallestPosOdd == 0:
						smallestPosOdd = arr[i]
					elif smallestPosOdd > arr[i]:
						smallestPosOdd = arr[i]
				elif arr[i] < 0:
					if largestNegOdd == 0:
						largestNegOdd = arr[i]
					elif largestNegOdd < arr[i]:
						largestNegOdd = arr[i]
		if sumPos % 2 == 1:
			return sumPos
		else:
			sum1 = sumPos - smallestPosOdd
			sum2 = sumPos + largestNegOdd
			if sum1 % 2 == 0 and sum2 % 2 == 1:
				return sum2
			if sum1 % 2 == 1 and sum2 % 2 == 0:
				return sum1
			if sum1 % 2 == 0 and sum2 % 2 == 0:
				return -1
			if sum1 > sum2:
				return sum1
			else:
				return sum2