There are two parallel roads, each containing N and M buckets, respectively. Each bucket may contain some balls. The balls in first road are given in an array a and balls in the second road in an array b. The buckets on both roads are kept in such a way that they are sorted according to the number of balls in them. Geek starts from the end of the road which has the bucket with a lower number of balls(i.e. if buckets are sorted in increasing order, then geek will start from the left side of the road).
Geek can change the road only at a point of intersection i.e. a point where buckets have the same number of balls on two roads. Help Geek collect the maximum number of balls.
 
Example 1:
Input: 
N = 5, M = 5
a[] = {1, 4, 5, 6, 8}
b[] = {2, 3, 4, 6, 9}
Output: 29
Explanation: The optimal way to get the 
maximum number of balls is to start from 
road 2. Get 2+3. Then switch at intersection 
point 4. Get 4+5+6. Then switch at intersection
point 6. Get 9. Total = 2+3+4+5+6+9 = 29.
Example 2:
Input:
N = 3, M = 3
a[] = {1, 2, 3}
b[] = {4, 5, 6}
Output: 15
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function maxBalls() which takes N, M, a[] and b[] as input parameters and returns the maximum number of balls that can be collected.
 
Expected Time Complexity: O(N+M)
Expected Auxililary Space: O(1)
 
Constraints:
1 ≤ N, M ≤ 10^{3}
1 ≤ a[i], b[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Greedy algorithms

Starter code: #User function Template for python3

class Solution:
    def maxBalls(self, N, M, a, b):
        # code here

Solutions:
class Solution:

	def maxBalls(self, N, M, a, b):
		i = 0
		j = 0
		(val1, val2) = (0, 0)
		(x, y) = (0, 0)
		while i < N and j < M:
			(x, y) = (a[i], b[j])
			if x < y:
				val1 = val1 + x
				i = i + 1
			elif y < x:
				val2 = val2 + y
				j = j + 1
			else:
				(x1, y1) = (0, 0)
				while i < N and a[i] == x:
					x1 = x1 + x
					i = i + 1
				while j < M and b[j] == y:
					y1 = y1 + y
					j = j + 1
				(val1, val2) = (max(val1 + x1, val1 + x1 + y1 - 2 * x, val2 + x1 + y1 - x), max(val2 + y1, val2 + x1 + y1 - 2 * x, val1 + x1 + y1 - x))
		while i < N:
			val1 = val1 + a[i]
			i = i + 1
		while j < M:
			val2 = val2 + b[j]
			j = j + 1
		ans = max(val1, val2)
		return ans


class Solution:

	def maxBalls(self, N, M, a, b):
		first = second = 0
		i = j = 0
		while i < N and j < M:
			if a[i] < b[j]:
				first += a[i]
				i += 1
			elif a[i] > b[j]:
				second += b[j]
				j += 1
			else:
				cur = a[i]
				count_a = count_b = 0
				while i < N and a[i] == cur:
					i += 1
					count_a += 1
				while j < M and b[j] == cur:
					j += 1
					count_b += 1
				first_temp = max(first + count_a * cur, second + (count_a + count_b - 1) * cur)
				second_temp = max(second + count_b * cur, first + (count_a + count_b - 1) * cur)
				if count_a > 1 and count_b > 1:
					first_temp = max(first_temp, first + (count_a + count_b - 2) * cur)
					second_temp = max(second_temp, second + (count_a + count_b - 2) * cur)
				first = first_temp
				second = second_temp
		while i < N:
			first += a[i]
			i += 1
		while j < M:
			second += b[j]
			j += 1
		return max(first, second)


class Solution:

	def maxBalls(self, N, M, a, b):
		i = j = 0
		sm = 0
		sm2 = sm1 = 0
		while i < N and j < M:
			if a[i] < b[j]:
				sm1 += a[i]
				i += 1
			elif a[i] > b[j]:
				sm2 += b[j]
				j += 1
			else:
				v = a[i]
				ca = cb = 0
				while i < N and a[i] == v:
					ca += 1
					i += 1
				while j < M and b[j] == v:
					cb += 1
					j += 1
				r0 = max(sm1 + ca * v, sm2 + (ca + cb - 1) * v)
				r1 = max(sm2 + cb * v, sm1 + (ca + cb - 1) * v)
				if ca > 1 and cb > 1:
					r0 = max(r0, sm1 + (ca + cb - 2) * v)
					r1 = max(r1, sm2 + (ca + cb - 2) * v)
				sm1 = r0
				sm2 = r1
		while i < N:
			sm1 += a[i]
			i += 1
		while j < M:
			sm2 += b[j]
			j += 1
		return max(sm1, sm2)


class Solution:

	def maxBalls(self, N, M, a, b):
		count = 0
		maxa = 0
		maxb = 0
		i = 0
		j = 0
		while i != len(a) and j != len(b):
			if a[i] < b[j]:
				maxa += a[i]
				i += 1
			elif b[j] < a[i]:
				maxb += b[j]
				j += 1
			else:
				v = a[i]
				ca = 0
				cb = 0
				while i < len(a) and a[i] == v:
					ca += 1
					i += 1
				while j < len(b) and b[j] == v:
					cb += 1
					j += 1
				r0 = max(maxa + ca * v, maxb + (ca + cb - 1) * v)
				r1 = max(maxb + cb * v, maxa + (ca + cb - 1) * v)
				if ca > 1 and cb > 1:
					r0 = max(r0, maxa + (ca + cb - 2) * v)
					r1 = max(r1, maxb + (ca + cb - 2) * v)
				maxa = r0
				maxb = r1
		while i < N:
			maxa += a[i]
			i += 1
		while j < M:
			maxb += b[j]
			j += 1
		return max(maxa, maxb)


class Solution:

	def maxBalls(self, n, m, A, B):
		i = 0
		j = 0
		(val1, val2) = (0, 0)
		(x, y) = (0, 0)
		while i < n and j < m:
			(x, y) = (A[i], B[j])
			if x < y:
				val1 = val1 + x
				i = i + 1
			elif y < x:
				val2 = val2 + y
				j = j + 1
			else:
				(x1, y1) = (0, 0)
				while i < n and A[i] == x:
					x1 = x1 + x
					i = i + 1
				while j < m and B[j] == y:
					y1 = y1 + y
					j = j + 1
				(val1, val2) = (max(val1 + x1, val1 + x1 + y1 - 2 * x, val2 + x1 + y1 - x), max(val2 + y1, val2 + x1 + y1 - 2 * x, val1 + x1 + y1 - x))
		while i < n:
			val1 = val1 + A[i]
			i = i + 1
		while j < m:
			val2 = val2 + B[j]
			j = j + 1
		ans = max(val1, val2)
		return ans


class Solution:

	def maxBalls(self, N, M, A, B):

		def _solve(sia, sib):
			if (sia, sib) in dp:
				return dp[sia, sib]
			(ia, ib) = (sia, sib)
			(ans, sa, sb) = (0, 0, 0)
			while ia < N and ib < M:
				if A[ia] == B[ib]:
					(v, tmpA, tmpB) = (A[ia], 0, 0)
					ix = ia
					sa += v
					while ix < N - 1 and A[ix + 1] == v:
						tmpA = max(tmpA, sa + _solve(ix + 1, ib + 1))
						ix += 1
						sa += v
					tmpA = max(tmpA, sa + _solve(ix + 1, ib + 1))
					ix = ib
					sb += v
					while ix < M - 1 and B[ix + 1] == v:
						tmpB = max(tmpB, sb + _solve(ia + 1, ix + 1))
						ix += 1
						sb += v
					tmpB = max(tmpB, sb + _solve(ia + 1, ix + 1))
					ans = max(tmpA, tmpB)
					dp[sia, sib] = ans
					return ans
				elif A[ia] < B[ib]:
					sa += A[ia]
					ia += 1
				else:
					sb += B[ib]
					ib += 1
			if ia < N:
				sa += sum(A[ia:])
				ans += max(sa, sb)
			elif ib < M:
				sb += sum(B[ib:])
				ans += max(sa, sb)
			dp[sia, sib] = ans
			return ans
		dp = {}
		ans = _solve(0, 0)
		return ans


class Solution:

	def maxBalls(self, N, M, a, b):
		i = 0
		j = 0
		R = [0, 0]
		new_ans1 = new_ans2 = 0
		while i < N and j < M:
			if a[i] < b[j]:
				R[0] += a[i]
				i += 1
			elif a[i] > b[j]:
				R[1] += b[j]
				j += 1
			else:
				v = a[i]
				ca = 0
				cb = 0
				while i < N and a[i] == v:
					ca += 1
					i += 1
				while j < M and b[j] == v:
					cb += 1
					j += 1
				r0 = max(R[0] + ca * v, R[1] + (ca + cb - 1) * v)
				r1 = max(R[1] + cb * v, R[0] + (ca + cb - 1) * v)
				if ca > 1 and cb > 1:
					r0 = max(r0, R[0] + (ca + cb - 2) * v)
					r1 = max(r1, R[1] + (ca + cb - 2) * v)
				R[0] = r0
				R[1] = r1
		while i < N:
			R[0] += a[i]
			i += 1
		while j < M:
			R[1] += b[j]
			j += 1
		return max(R[0], R[1], max(sum(a), sum(b)))


class Solution:

	def maxBalls(self, n, m, a, b):
		i = 0
		j = 0
		s1 = 0
		s2 = 0
		while i < N and j < M:
			if a[i] < b[j]:
				s1 += a[i]
				i += 1
			elif a[i] > b[j]:
				s2 += b[j]
				j += 1
			else:
				c1 = 0
				c2 = 0
				temp = a[i]
				while i < N and a[i] == temp:
					c1 += 1
					i += 1
				while j < M and b[j] == temp:
					c2 += 1
					j += 1
				r1 = max(s1 + c1 * temp, s2 + (c1 + c2 - 1) * temp)
				r2 = max(s2 + c2 * temp, s1 + (c1 + c2 - 1) * temp)
				if c1 > 1 and c2 > 1:
					r1 = max(r1, s1 + (c1 + c2 - 2) * temp)
					r2 = max(r2, s2 + (c1 + c2 - 2) * temp)
				s1 = r1
				s2 = r2
		while i < N:
			s1 += a[i]
			i += 1
		while j < M:
			s2 += b[j]
			j += 1
		return max(s1, s2)


class Solution:

	def maxBalls(self, N, M, a, b):
		if a[0] > a[-1]:
			a = a[::-1]
		if b[0] > b[-1]:
			b = b[::-1]
		curr1 = 0
		curr2 = 0
		i = 0
		j = 0
		while i < N and j < M:
			if a[i] == b[j]:
				temp = a[i]
				c1 = 0
				c2 = 0
				while i < N and a[i] == temp:
					c1 += 1
					i += 1
				while j < M and b[j] == temp:
					c2 += 1
					j += 1
				if curr1 > curr2:
					curr2 = curr1 + (c1 + c2 - 1) * temp
					if c1 > 1:
						curr1 += (c1 + c2 - 2) * temp
					else:
						curr1 += temp
				else:
					curr1 = curr2 + (c1 + c2 - 1) * temp
					if c2 > 1:
						curr2 += (c1 + c2 - 2) * temp
					else:
						curr2 += temp
			elif a[i] < b[j]:
				curr1 += a[i]
				i += 1
			else:
				curr2 += b[j]
				j += 1
		while i < N:
			curr1 += a[i]
			i += 1
		while j < M:
			curr2 += b[j]
			j += 1
		ans = max(curr1, curr2)
		return ans