Given two sorted arrays such the arrays may have some common elements. Find the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays. You can start from any array and switch from one array to another array only at common elements. 
Example 1:
Input:
M = 5, N = 4
Arr1[] = {2, 3, 7, 10, 12}
Arr2[] = {1, 5, 7, 8}
Output: 35
Explanation: 35 is sum of 1 + 5 + 7 + 10 +
12. We start from the first element of
Arr2 which is 1, then we move to 5, then 7
From 7, we switch to Arr1 (as 7 is common)
and traverse 10 and 12.
Example 2:
Input:
M = 2, N = 3
Arr1[] = {10, 12}
Arr2[] = {5, 7, 9}
Output: 22
Explanation: 22 is the sum of 10 and 12.
Since there is no common element, we need
to take all elements from the array with
more sum.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxPathSum() which takes two arrays of integers arr1, arr2, m and n as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(M+N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= M, N <= 10^{5}
0 <= Arr1[i], Arr2[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3
class Solution:

	def maxPathSum(self,arr1, arr2, m, n):
		# code here

Solutions:
class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		sum1 = 0
		sum2 = 0
		ans = 0
		(i, j) = (0, 0)
		while i < m or j < n:
			if i == m:
				sum2 += arr2[j]
				j += 1
			elif j == n:
				sum1 += arr1[i]
				i += 1
			elif arr1[i] < arr2[j]:
				sum1 += arr1[i]
				i += 1
			elif arr1[i] > arr2[j]:
				sum2 += arr2[j]
				j += 1
			else:
				ans += max(sum1, sum2) + arr1[i]
				i += 1
				j += 1
				(sum1, sum2) = (0, 0)
		return ans + max(sum1, sum2)


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		(sum1, sum2) = (0, 0)
		max_sum = 0
		(i, j) = (0, 0)
		while i < m and j < n:
			if arr1[i] < arr2[j]:
				sum1 += arr1[i]
				i += 1
			elif arr2[j] < arr1[i]:
				sum2 += arr2[j]
				j += 1
			else:
				sum1 += arr1[i]
				sum2 += arr2[j]
				max_sum += max(sum1, sum2)
				(sum1, sum2) = (0, 0)
				i += 1
				j += 1
		if i == m:
			while j < n:
				sum2 += arr2[j]
				j += 1
			max_sum += max(sum1, sum2)
		elif j == n:
			while i < m:
				sum1 += arr1[i]
				i += 1
			max_sum += max(sum1, sum2)
		else:
			max_sum += max(sum1, sum2)
		return max_sum


class Solution:

	def maxPathSum(self, a1, a2, m, n):
		sum1 = 0
		sum2 = 0
		(i, j) = (0, 0)
		ans = 0
		while i < m and j < n:
			if a1[i] < a2[j]:
				sum1 += a1[i]
				i += 1
			elif a1[i] > a2[j]:
				sum2 += a2[j]
				j += 1
			else:
				if sum1 > sum2:
					ans += sum1
				else:
					ans += sum2
				ans += a1[i]
				(sum1, sum2) = (0, 0)
				i += 1
				j += 1
		if i == m:
			while j < n:
				sum2 += a2[j]
				j += 1
		else:
			while i < m:
				sum1 += a1[i]
				i += 1
		if sum1 > sum2:
			ans += sum1
		else:
			ans += sum2
		return ans


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		output = 0
		summa1 = 0
		summa2 = 0
		i = 0
		j = 0
		while i < m and j < n:
			if arr1[i] < arr2[j]:
				summa1 += arr1[i]
				i += 1
			elif arr1[i] > arr2[j]:
				summa2 += arr2[j]
				j += 1
			else:
				output += max(summa1, summa2) + arr1[i]
				summa1 = 0
				summa2 = 0
				i += 1
				j += 1
		while i < m:
			summa1 += arr1[i]
			i += 1
		while j < n:
			summa2 += arr2[j]
			j += 1
		output += max(summa1, summa2)
		return output


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		s1 = 0
		s2 = 0
		i = 0
		j = 0
		res = 0
		while i < m and j < n:
			if arr1[i] < arr2[j]:
				s1 += arr1[i]
				i += 1
			elif arr1[i] > arr2[j]:
				s2 += arr2[j]
				j += 1
			else:
				while i < m and j < n and (arr1[i] == arr2[j]):
					s1 += arr1[i]
					s2 += arr2[j]
					i += 1
					j += 1
				res += max(s1, s2)
				s1 = 0
				s2 = 0
		while i < m:
			s1 += arr1[i]
			i += 1
		while j < n:
			s2 += arr2[j]
			j += 1
		res += max(s1, s2)
		return res


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		i = 0
		j = 0
		s1 = 0
		s2 = 0
		res = 0
		while i < len(arr1) and j < len(arr2):
			if arr1[i] == arr2[j]:
				res += max(s1, s2)
				res += arr1[i]
				(s1, s2) = (0, 0)
				i += 1
				j += 1
			elif arr1[i] < arr2[j]:
				s1 += arr1[i]
				i += 1
			else:
				s2 += arr2[j]
				j += 1
		s1 += sum(arr1[i:])
		s2 += sum(arr2[j:])
		return res + max(s1, s2)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(m, n) = list(map(int, input().strip().split()))
		arr1 = list(map(int, input().strip().split()))
		arr2 = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.maxPathSum(arr1, arr2, m, n)
		print(ans)
		tc -= 1


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		(i, j, total_sum) = (0, 0, 0)
		(sum1, sum2) = (0, 0)
		while i < m and j < n:
			if arr1[i] == arr2[j]:
				total_sum = total_sum + max(sum1, sum2) + arr1[i]
				(sum1, sum2) = (0, 0)
				i = i + 1
				j = j + 1
				continue
			if arr1[i] < arr2[j]:
				sum1 = sum1 + arr1[i]
				i = i + 1
			else:
				sum2 = sum2 + arr2[j]
				j = j + 1
		while i < m:
			sum1 = sum1 + arr1[i]
			i = i + 1
		while j < n:
			sum2 = sum2 + arr2[j]
			j = j + 1
		total_sum = total_sum + max(sum1, sum2)
		return total_sum
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(m, n) = list(map(int, input().strip().split()))
		arr1 = list(map(int, input().strip().split()))
		arr2 = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.maxPathSum(arr1, arr2, m, n)
		print(ans)
		tc -= 1


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		arr1.append(float('inf'))
		arr2.append(float('inf'))
		i = 0
		j = 0
		res = 0
		while i < len(arr1) and j < len(arr2):
			t1 = 0
			t2 = 0
			while arr1[i] != arr2[j]:
				if arr1[i] < arr2[j]:
					t1 += arr1[i]
					i += 1
				elif arr1[i] > arr2[j]:
					t2 += arr2[j]
					j += 1
			if arr1[i] != float('inf'):
				t1 += arr1[i]
				t2 += arr2[j]
			i += 1
			j += 1
			res += max(t1, t2)
		return res


from collections import defaultdict

class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		d = defaultdict(int)
		req = []
		for i in range(len(arr1)):
			if arr1[i] not in d:
				d[arr1[i]] = i
		for j in range(len(arr2)):
			if arr2[j] in d:
				req.append([d[arr2[j]], j])
				del d[arr2[j]]
		prefixs1 = defaultdict(int)
		prefixs1[-1] = 0
		s = 0
		for i in range(len(arr1)):
			s += arr1[i]
			prefixs1[i] = s
		prefixs2 = defaultdict(int)
		prefixs2[-1] = 0
		s = 0
		for i in range(len(arr2)):
			s += arr2[i]
			prefixs2[i] = s
		end1 = 0
		end2 = 0
		ans = 0
		for x in req:
			ans += max(prefixs1[x[0]] - prefixs1[end1 - 1], prefixs2[x[1]] - prefixs2[end2 - 1])
			end1 = x[0] + 1
			end2 = x[1] + 1
		ans1 = 0
		ans2 = 0
		while end1 < len(arr1):
			ans1 += arr1[end1]
			end1 += 1
		while end2 < len(arr2):
			ans2 += arr2[end2]
			end2 += 1
		return ans + max(ans1, ans2)


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		m = len(arr1)
		n = len(arr2)
		prefix1 = [0] * (m + 1)
		prefix2 = [0] * (n + 1)
		prefix1[1] = arr1[0]
		prefix2[1] = arr2[0]
		mp = {}
		for i in range(m + 1):
			if i < m and arr1[i] not in mp:
				mp[arr1[i]] = i + 1
			if i > 1:
				prefix1[i] = prefix1[i - 1] + arr1[i - 1]
		vec = []
		for i in range(n + 1):
			if i < n and arr2[i] in mp:
				vec.append((mp[arr2[i]], i + 1))
				del mp[arr2[i]]
			if i > 1:
				prefix2[i] = prefix2[i - 1] + arr2[i - 1]
		end1 = 1
		end2 = 1
		res = 0
		for (r1, r2) in vec:
			max1 = prefix1[r1] - prefix1[end1 - 1]
			max2 = prefix2[r2] - prefix2[end2 - 1]
			res += max(max1, max2)
			end1 = r1 + 1
			end2 = r2 + 1
		temp1 = prefix1[m] - prefix1[end1 - 1]
		temp2 = prefix2[n] - prefix2[end2 - 1]
		res += max(temp1, temp2)
		return res


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		i = 0
		j = 0
		tot1 = 0
		tot2 = 0
		final = 0
		while i < len(arr1) and j < len(arr2):
			if arr1[i] < arr2[j]:
				tot1 += arr1[i]
				i += 1
			elif arr1[i] > arr2[j]:
				tot2 += arr2[j]
				j += 1
			else:
				final += max(tot1, tot2) + arr1[i]
				tot1 = 0
				tot2 = 0
				i += 1
				j += 1
		while i < len(arr1):
			tot1 += arr1[i]
			i += 1
		while j < len(arr2):
			tot2 += arr2[j]
			j += 1
		final += max(tot1, tot2)
		return final


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		(lengthArr1, lengthArr2) = (m, n)
		i = 0
		j = 0
		sum1 = 0
		sum2 = 0
		result = 0
		while i < lengthArr1 and j < lengthArr2:
			if arr1[i] < arr2[j]:
				sum1 += arr1[i]
				i += 1
			elif arr1[i] > arr2[j]:
				sum2 += arr2[j]
				j += 1
			else:
				result += max(sum1, sum2) + arr1[i]
				sum2 = 0
				sum1 = 0
				j += 1
				i += 1
		if i < lengthArr1:
			sum1 += sum(arr1[i:])
		if j < lengthArr2:
			sum2 += sum(arr2[j:])
		result += max(sum1, sum2)
		return result


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		(sx, sy, Max) = (0, 0, 0)
		(i, j) = (0, 0)
		while i < m and j < n:
			if arr1[i] < arr2[j]:
				sx += arr1[i]
				i += 1
			elif arr2[j] < arr1[i]:
				sy += arr2[j]
				j += 1
			else:
				Max += max(sx, sy) + arr1[i]
				i += 1
				j += 1
				(sx, sy) = (0, 0)
		while i < m:
			sx += arr1[i]
			i += 1
		while j < n:
			sy += arr2[j]
			j += 1
		Max += max(sx, sy)
		return Max


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		common_els = []
		set2 = set(arr2)
		for el in arr1:
			if el in set2:
				common_els.append(el)
		if not common_els:
			return max(sum(arr1), sum(arr2))
		i1 = 0
		i2 = 0
		tot_sum = 0
		for ce in common_els:
			cum_sum_1 = 0
			while arr1[i1] < ce:
				cum_sum_1 += arr1[i1]
				i1 += 1
			cum_sum_2 = 0
			while arr2[i2] < ce:
				cum_sum_2 += arr2[i2]
				i2 += 1
			tot_sum += max(cum_sum_1, cum_sum_2)
		cum_sum_1 = 0
		for i in range(i1, m):
			cum_sum_1 += arr1[i]
		cum_sum_2 = 0
		for i in range(i2, n):
			cum_sum_2 += arr2[i]
		tot_sum += max(cum_sum_1, cum_sum_2)
		return tot_sum


class Solution:

	def maxPathSum(self, arr1, arr2, m, n):
		i = 0
		j = 0
		curr_sum1 = 0
		curr_sum2 = 0
		main_sum = 0
		while i < m and j < n:
			if arr1[i] < arr2[j]:
				curr_sum1 += arr1[i]
				i += 1
			elif arr1[i] > arr2[j]:
				curr_sum2 += arr2[j]
				j += 1
			else:
				main_sum += max(curr_sum1, curr_sum2)
				curr_sum1 = arr1[i]
				curr_sum2 = arr1[i]
				i += 1
				j += 1
		while i < m:
			curr_sum1 += arr1[i]
			i += 1
		while j < n:
			curr_sum2 += arr2[j]
			j += 1
		main_sum += max(curr_sum1, curr_sum2)
		return main_sum


class Solution:

	def maxPathSum(self, li1, li2, n, m):
		i = 0
		j = 0
		(sum1, sum2) = (0, 0)
		max_sum = 0
		while i < n and j < m:
			if li1[i] == li2[j]:
				max_sum += max(sum1, sum2) + li1[i]
				(sum1, sum2) = (0, 0)
				i = i + 1
				j = j + 1
			elif li1[i] < li2[j]:
				sum1 += li1[i]
				i = i + 1
			elif li1[i] > li2[j]:
				sum2 += li2[j]
				j = j + 1
		if i == n:
			for k in range(j, m):
				sum2 += li2[k]
		elif j == m:
			for k in range(i, n):
				sum1 += li1[k]
		max_sum += max(sum1, sum2)
		return max_sum