Given two sorted arrays A and B of size M and N respectively. Each array may have some elements in common with the other array. Find the maximum sum of a path from the beginning of any array to the end of any of the two arrays. We can switch from one array to another array only at the common elements.Both the arrays are sorted.
Note: Only one repeated value is considered in the valid path sum.
Example 1:
Input:
M = 5, N = 4
A[] = {2,3,7,10,12}
B[] = {1,5,7,8}
Output: 35
Explanation: The path will be 1+5+7+10+12
= 35.
Example 2:
Input:
M = 3, N = 3
A[] = {1,2,3}
B[] = {3,4,5}
Output: 15
Explanation: The path will be 1+2+3+4+5=15.
Your Task:
You don't need to read input or print anything. Complete the function max_path_sum() which takes the two arrays A and B along with their sizes M and N as input parameters. It returns the maximum path sum.
Expected Time Complexity: O(M + N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= M,N <= 10^{4}
1 <= A[i], B[i] <= 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #Your task is to complete this function

#Function should return an integer denoting the required answer

class Solution:

    def maxSumPath(self, arr1, arr2, m, n):

        #code here

Solutions:
class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		maxsumpath = []
		path1 = []
		path2 = []
		i = 0
		j = 0
		while i < m and j < n:
			if arr1[i] < arr2[j]:
				path1.append(arr1[i])
				i += 1
			elif arr2[j] < arr1[i]:
				path2.append(arr2[j])
				j += 1
			elif arr1[i] == arr2[j]:
				sum1 = sum(path1)
				sum2 = sum(path2)
				if sum1 >= sum2:
					maxsumpath += path1
				else:
					maxsumpath += path2
				maxsumpath += [arr1[i]]
				path1 = []
				path2 = []
				i += 1
				j += 1
		for k in range(i, m):
			path1.append(arr1[k])
		for k in range(j, n):
			path2.append(arr2[k])
		sum1 = sum(path1)
		sum2 = sum(path2)
		if sum1 >= sum2:
			maxsumpath += path1
		else:
			maxsumpath += path2
		return sum(maxsumpath)


class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		(i, j) = (0, 0)
		s1 = 0
		s2 = 0
		ans = 0
		while i < m - 1 and j < n - 1:
			while arr1[i] < arr2[j] and i < m:
				s1 += arr1[i]
				i += 1
			while arr2[j] < arr1[i] and j < n:
				s2 += arr2[j]
				j += 1
			if arr1[i] == arr2[j]:
				s1 += arr1[i]
				s2 += arr2[j]
				ans += max(s1, s2)
				i += 1
				j += 1
				(s1, s2) = (0, 0)
		while i < m:
			s1 += arr1[i]
			i += 1
		while j < n:
			s2 += arr2[j]
			j += 1
		ans += max(s1, s2)
		return ans


class Solution:

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


class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		A_i = 0
		B_j = 0
		sum1 = 0
		sum2 = 0
		res = 0
		while A_i < m and B_j < n:
			if arr1[A_i] > arr2[B_j]:
				sum2 += arr2[B_j]
				B_j += 1
			elif arr2[B_j] > arr1[A_i]:
				sum1 += arr1[A_i]
				A_i += 1
			else:
				res += max(sum1, sum2) + arr1[A_i]
				sum1 = 0
				sum2 = 0
				A_i += 1
				B_j += 1
		while A_i < m:
			sum1 += arr1[A_i]
			A_i += 1
		while B_j < n:
			sum2 += arr2[B_j]
			B_j += 1
		res += max(sum1, sum2)
		return res


class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		(max_sum, sum1, sum2) = (0, 0, 0)
		(pointer1, pointer2) = (0, 0)
		while pointer1 < m and pointer2 < n:
			if arr1[pointer1] == arr2[pointer2]:
				max_sum += arr1[pointer1]
				pointer1 += 1
				pointer2 += 1
				max_sum += max(sum1, sum2)
				(sum1, sum2) = (0, 0)
			elif arr1[pointer1] > arr2[pointer2]:
				sum2 += arr2[pointer2]
				pointer2 += 1
			elif arr1[pointer1] < arr2[pointer2]:
				sum1 += arr1[pointer1]
				pointer1 += 1
		while pointer1 < m:
			sum1 += arr1[pointer1]
			pointer1 += 1
		while pointer2 < n:
			sum2 += arr2[pointer2]
			pointer2 += 1
		max_sum += max(sum1, sum2)
		return max_sum


from collections import defaultdict
import numpy as np

class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		if len(set(arr1).intersection(arr2)) == 0:
			return max(sum(arr1), sum(arr2))
		total = 0
		sum1 = 0
		sum2 = 0
		(i, j) = (0, 0)
		while i < len(arr1) and j < len(arr2):
			if arr1[i] < arr2[j]:
				sum1 += arr1[i]
				i += 1
			elif arr1[i] > arr2[j]:
				sum2 += arr2[j]
				j += 1
			else:
				sum1 += arr1[i]
				sum2 += arr2[j]
				total += max(sum1, sum2)
				(sum1, sum2) = (0, 0)
				i += 1
				j += 1
		if i < len(arr1):
			sum1 += sum(arr1[i:])
		elif j < len(arr2):
			sum2 += sum(arr2[j:])
		total += max(sum1, sum2)
		return total


class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		sumB = sumA = answer = i = j = 0
		while i < m and j < n:
			if arr1[i] < arr2[j]:
				sumA += arr1[i]
				i += 1
			elif arr1[i] > arr2[j]:
				sumB += arr2[j]
				j += 1
			else:
				answer += max(sumA, sumB) + arr1[i]
				sumA = sumB = 0
				i += 1
				j += 1
		while i < m:
			sumA += arr1[i]
			i += 1
		while j < n:
			sumB += arr2[j]
			j += 1
		answer += max(sumA, sumB)
		return answer


class Solution:

	def maxSumPath(self, array1, array2, m, n):
		(i, j) = (0, 0)
		(sum1, sum2, result) = (0, 0, 0)
		while i < m and j < n:
			if array1[i] < array2[j]:
				sum1 += array1[i]
				i += 1
			elif array1[i] > array2[j]:
				sum2 += array2[j]
				j += 1
			else:
				result += max(sum1, sum2) + array1[i]
				(sum1, sum2) = (0, 0)
				i += 1
				j += 1
		while i < m:
			sum1 += array1[i]
			i += 1
		while j < n:
			sum2 += array2[j]
			j += 1
		result += max(sum1, sum2)
		return result


class Solution:

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


class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		(result, sum1, sum2) = (0, 0, 0)
		i = 0
		j = 0
		while i < m or j < n:
			if j == n:
				sum1 += arr1[i]
				i += 1
			elif i == m:
				sum2 += arr2[j]
				j += 1
			elif 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]
				sum1 = 0
				sum2 = 0
				i += 1
				j += 1
		result += max(sum1, sum2)
		return result


class Solution:

	def maxSumPath(self, a, b, m, n):
		s1 = 0
		s2 = 0
		i = 0
		j = 0
		h = 0
		while i < m and j < n:
			if a[i] < b[j]:
				s1 += a[i]
				i += 1
			elif a[i] > b[j]:
				s2 += b[j]
				j += 1
			else:
				h = max(s1, s2) + a[i] + h
				s1 = 0
				s2 = 0
				i += 1
				j += 1
		while i < m:
			s1 += a[i]
			i += 1
		while j < n:
			s2 += b[j]
			j += 1
		h = max(s1, s2) + h
		return h


class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		p1 = p2 = 0
		main_sum = 0
		(s1, s2) = (arr1[0], arr2[0])
		while p1 < m or p2 < n:
			if p1 >= m:
				s2 += sum(arr2[p2 + 1:])
				main_sum += max(s1, s2)
				break
			if p2 >= n:
				s1 += sum(arr1[p1 + 1:])
				main_sum += max(s1, s2)
				break
			(e1, e2) = (arr1[p1], arr2[p2])
			if e1 < e2:
				p1 += 1
				s1 += arr1[p1] if p1 < m else 0
			elif e2 < e1:
				p2 += 1
				s2 += arr2[p2] if p2 < n else 0
			else:
				main_sum += max(s1, s2)
				p1 += 1
				p2 += 1
				s1 = arr1[p1] if p1 < m else 0
				s2 = arr2[p2] if p2 < n else 0
		return main_sum


class Solution:

	def maxSumPath(self, a, b, m, n):
		sum1 = 0
		sum2 = 0
		ans = 0
		i = j = 0
		while i < m and j < n:
			if a[i] < b[j]:
				sum1 += a[i]
				i += 1
			elif a[i] > b[j]:
				sum2 += b[j]
				j += 1
			else:
				ans += a[i] + max(sum1, sum2)
				sum1 = sum2 = 0
				i += 1
				j += 1
		sum1 += sum(a[i:])
		sum2 += sum(b[j:])
		ans += max(sum1, sum2)
		return ans


class Solution:

	def maxSumPath(self, a, b, m, n):
		(suma, sumb) = (0, 0)
		(i, j) = (0, 0)
		result = 0
		while i < m and j < n:
			if a[i] < b[j]:
				suma += a[i]
				i += 1
			elif b[j] < a[i]:
				sumb += b[j]
				j += 1
			else:
				result += max(suma, sumb) + a[i]
				(suma, sumb) = (0, 0)
				i += 1
				j += 1
		while i < m:
			suma += a[i]
			i += 1
		while j < n:
			sumb += b[j]
			j += 1
		result = result + max(suma, sumb)
		return result


class Solution:

	def maxSumPath(self, ar1, ar2, m, n):
		(i, j) = (0, 0)
		(result, sum1, sum2) = (0, 0, 0)
		while i < m and j < n:
			if ar1[i] < ar2[j]:
				sum1 += ar1[i]
				i += 1
			elif ar1[i] > ar2[j]:
				sum2 += ar2[j]
				j += 1
			else:
				result += max(sum1, sum2) + ar1[i]
				sum1 = 0
				sum2 = 0
				i += 1
				j += 1
		while i < m:
			sum1 += ar1[i]
			i += 1
		while j < n:
			sum2 += ar2[j]
			j += 1
		result += max(sum1, sum2)
		return result


from collections import Counter

class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		s1 = 0
		s2 = 0
		i = 0
		j = 0
		h = 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:
				h = max(s1, s2) + arr1[i] + h
				s1 = 0
				s2 = 0
				i += 1
				j += 1
		while i < m:
			s1 += arr1[i]
			i += 1
		while j < n:
			s2 += arr2[j]
			j += 1
		h = max(s1, s2) + h
		return h


class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		a = 0
		b = 0
		p1 = 0
		p2 = 0
		ans = 0
		while p1 != m and p2 != n:
			if arr1[p1] == arr2[p2]:
				ans += max(a, b)
				ans += arr1[p1]
				a = 0
				b = 0
				p1 += 1
				p2 += 1
			elif arr1[p1] > arr2[p2]:
				b += arr2[p2]
				p2 += 1
			elif arr1[p1] < arr2[p2]:
				a += arr1[p1]
				p1 += 1
		while p1 < m:
			a += arr1[p1]
			p1 += 1
		while p2 < n:
			b += arr2[p2]
			p2 += 1
		return ans + max(a, b)


class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		s1 = 0
		s2 = 0
		i = 0
		j = 0
		result = 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:
				result += max(s1, s2) + arr1[i]
				s1 = 0
				s2 = 0
				i += 1
				j += 1
		while i < m:
			s1 += arr1[i]
			i += 1
		while j < n:
			s2 += arr2[j]
			j += 1
		result += max(s1, s2)
		return result


class Solution:

	def maxSumPath(self, a1, a2, m, n):
		s1 = 0
		s2 = 0
		ans = 0
		i = 0
		j = 0
		while i < m and j < n:
			if a1[i] == a2[j]:
				ans += max(s1, s2) + a1[i]
				s1 = 0
				s2 = 0
				i += 1
				j += 1
			elif a1[i] > a2[j]:
				s2 += a2[j]
				j += 1
			else:
				s1 += a1[i]
				i += 1
		while i < m:
			s1 += a1[i]
			i += 1
		while j < n:
			s2 += a2[j]
			j += 1
		return ans + max(s1, s2)


class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		left = 0
		right = 0
		leftS = 0
		rightS = 0
		while left < m and right < n:
			if arr1[left] < arr2[right]:
				leftS += arr1[left]
				left += 1
			elif arr1[left] > arr2[right]:
				rightS += arr2[right]
				right += 1
			else:
				leftS = max(leftS, rightS) + arr1[left]
				rightS = leftS
				left += 1
				right += 1
		while left < m:
			leftS += arr1[left]
			left += 1
		while right < n:
			rightS += arr2[right]
			right += 1
		return max(leftS, rightS)


class Solution:

	def maxSumPath(self, a1, a2, m, n):
		i = 0
		j = 0
		x = 0
		y = 0
		res = 0
		while i < len(a1) and j < len(a2):
			if a1[i] == a2[j]:
				res = res + max(x, y) + a1[i]
				x = 0
				y = 0
				i = i + 1
				j = j + 1
			elif a1[i] < a2[j]:
				x = x + a1[i]
				i = i + 1
			elif a1[i] > a2[j]:
				y = y + a2[j]
				j = j + 1
		x = x + sum(a1[i:])
		y = y + sum(a2[j:])
		return res + max(x, y)


class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		(i, j, total, sum1, sum2, prev1, prev2) = (0, 0, 0, 0, 0, 0, 0)
		while i < len(arr1) and j < len(arr2):
			if arr1[i] == arr2[j]:
				total += max(sum1, sum2)
				(prev1, prev2) = (i, j)
				(sum1, sum2) = (0, 0)
			if arr1[i] > arr2[j]:
				sum2 += arr2[j]
				j += 1
			else:
				sum1 += arr1[i]
				i += 1
		total += max(sum(arr1[prev1:]), sum(arr2[prev2:]))
		return total


from collections import defaultdict

class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		d = defaultdict(int)
		d1 = defaultdict(int)
		d2 = defaultdict(int)
		d3 = defaultdict(int)
		d4 = defaultdict(int)
		msp = 0
		as1 = set(arr1)
		as2 = set(arr2)
		cp = list(as1.intersection(as2))
		for i in arr1:
			d3[i] += 1
		for i in arr2:
			d4[i] += 1
		for i in cp:
			mi = min(d3[i], d4[i])
			d[i] = mi
			d1[i] = mi
			d2[i] = mi
		bda = defaultdict(int)
		bdb = defaultdict(int)
		sa = 0
		sb = 0
		for i in range(m):
			if d[arr1[i]] != 0:
				bda[arr1[i]] = sa
				if d[arr1[i]] == 1:
					sa = 0
				d[arr1[i]] -= 1
			else:
				sa += arr1[i]
		for i in range(n):
			if d1[arr2[i]] != 0:
				bdb[arr2[i]] = sb
				if d1[arr2[i]] == 1:
					sb = 0
				d1[arr2[i]] -= 1
			else:
				sb += arr2[i]
		for i in cp:
			msp = msp + i * d2[i] + max(bda[i], bdb[i])
		msp += max(sa, sb)
		return msp


from collections import defaultdict

class Solution:

	def maxSumPath(self, arr1, arr2, m, n):
		(i, j) = (0, 0)
		(result, sum1, sum2) = (0, 0, 0)
		while i < m and j < n:
			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)
				(sum1, sum2) = (0, 0)
				while i < m and j < n and (arr1[i] == arr2[j]):
					result += arr1[i]
					i += 1
					j += 1
		while i < m:
			sum1 += arr1[i]
			i += 1
		while j < n:
			sum2 += arr2[j]
			j += 1
		result += max(sum1, sum2)
		return result


class Solution:

	def maxSumPath(self, a, b, m, n):
		(sum1, sum2, maxSum) = (0, 0, 0)
		end1 = 0
		(i, j) = (0, 0)
		flag = False
		while i < m and j < n:
			if a[i] < b[j] and end1 != 1:
				sum1 += a[i]
				i += 1
			elif a[i] > b[j] and end1 != 2:
				sum2 += b[j]
				j += 1
			elif a[i] == b[j]:
				flag = True
				maxSum += max(sum1, sum2) + a[i]
				(sum1, sum2) = (0, 0)
				i += 1
				j += 1
		while i < m:
			sum1 += a[i]
			i += 1
		while j < n:
			sum2 += b[j]
			j += 1
		maxSum += max(sum1, sum2)
		return maxSum