You have a rectangular grid mat of dimension 2 x N. You need to find out the maximum sum such that no two chosen numbers are adjacent, vertically, diagonally or horizontally.
Example 1:
Input: N = 3
mat = {{1, 4, 5}, 
       {2, 0, 0}}
Output: 7
Explaination: Optimal choice is (2, 5).
Example 2:
Input: N = 2
mat = {{1, 2}, 
       {3, 4}}
Output: 4
Explaination: Optimal choice is (4).
Your Task:
You do not need to read input or print anything. Your task is to complete the function maxSum() which takes the value N and grid mat as input parameters and returns the maximum sum.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10000
1 ≤ mat[i][j] ≤ 70

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def maxSum(self, N, mat):
        # code here

Solutions:
class Solution:

	def maxSum(self, N, mat):
		dp = [-1] * N
		if N == 1:
			return max(mat[0][0], mat[1][0])
		dp[0] = max(0, mat[0][0], mat[1][0])
		dp[1] = max(dp[0], mat[0][1], mat[1][1])
		for i in range(2, N):
			dp[i] = max(max(mat[0][i], mat[1][i]) + dp[i - 2], dp[i - 1])
		return dp[N - 1]


class Solution:

	def maxSum(self, N, mat):
		secondLast = max(0, mat[0][0], mat[1][0])
		if N == 1:
			return last
		last = max(secondLast, mat[0][1], mat[1][1])
		i = 2
		while i < N:
			tmp = last
			last = max(max(mat[0][i], mat[1][i]) + secondLast, last)
			secondLast = tmp
			i += 1
		return last


class Solution:

	def maxSum(self, N, mat):
		if N == 1:
			return max(mat[0][0], mat[1][0])
		(arr, dp) = ([], [0] * 2 * N)
		for i in range(N):
			arr.append(mat[0][i])
			arr.append(mat[1][i])
		dp[0] = arr[0]
		dp[1] = max(arr[0], arr[1])
		dp[2] = max(arr[0], arr[1], arr[2])
		dp[3] = max(arr[0], arr[1], arr[2], arr[3])
		for i in range(4, 2 * N):
			dp[i] = max(dp[i - 1], arr[i] + (dp[i - 4] if i % 2 else dp[i - 3]))
		return dp[-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def __init__(self):
		self.Ans = []

	def MaxSum(self, i, n, a):
		if i >= n:
			return 0
		if self.Ans[i] != -1:
			return self.Ans[i]
		self.Ans[i] = max(max(a[0][i], a[1][i]) + self.MaxSum(i + 2, n, a), self.MaxSum(i + 1, n, a))
		return self.Ans[i]

	def maxSum(self, N, mat):
		self.Ans = [-1] * (N + 1)
		return self.MaxSum(0, N, mat)


class Solution:

	def maxSum(self, N, mat):
		(first, second) = (-1, -1)
		if N == 1:
			return max(mat[0][0], mat[1][0])
		first = max(0, max(mat[0][0], mat[1][0]))
		second = max(first, max(mat[0][1], mat[1][1]))
		if N == 2:
			return second
		for i in range(2, N):
			ai = max(mat[0][i], mat[1][i])
			curr = max(ai + first, second)
			first = second
			second = curr
		return second


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def maxSum(self, N, mat):
		f = max(0, max(mat[0][0], mat[1][0]))
		if N == 1:
			return f
		s = max(f, max(mat[0][1], mat[1][1]))
		for i in range(2, N):
			(f, s) = (s, max(f + max(mat[0][i], mat[1][i]), s))
		return s


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def find(self, mat, n, i):
		if i >= n:
			return 0
		if self.arr[i] != -1:
			return self.arr[i]
		self.arr[i] = max(max(mat[0][i], mat[1][i]) + self.find(mat, n, i + 2), self.find(mat, n, i + 1))
		return self.arr[i]

	def maxSum(self, N, mat):
		self.arr = [-1 for i in range(N)]
		return self.find(mat, N, 0)


class Solution:

	def maxSum(self, n, mat):
		dp = [0] * n
		dp[0] = max(mat[0][0], mat[1][0])
		if n > 1:
			for i in range(1, n):
				take = max(mat[0][i], mat[1][i]) + dp[i - 2]
				notake = dp[i - 1]
				dp[i] = max(take, notake)
		return dp[n - 1]


class Solution:

	def maxSum(self, n, a):
		b = max(a[0][0], a[1][0])
		if n == 1:
			return b
		c = max(max(a[0][1], a[1][1]), b)
		for i in range(2, n):
			(b, c) = (c, max(max(a[0][i], a[1][i]) + b, c))
		return c


from functools import lru_cache

class Solution:

	def maxSum(self, N, mat):
		dp = [0] * N
		dp[0] = max(mat[0][0], mat[1][0])
		dp[1] = max(mat[0][1], mat[1][1])
		result = max(dp[0], dp[1])
		for i in range(2, N):
			dp[i] = max(dp[i - 2] + mat[0][i], dp[i - 2] + mat[1][i])
			result = max(dp[i], result)
			dp[i - 1] = max(dp[i - 1], dp[i - 2])
		return result


import math

class Solution:

	def maxSum(self, N, mat):
		f = max(mat[0][0], mat[1][0], 0)
		s = max(f, mat[0][1], mat[1][1])
		mod = pow(10, 9) + 7
		if N == 2:
			return max(f, s)
		for i in range(2, N):
			curr = max(max(mat[0][i], mat[1][i]) + f, s)
			curr = curr % mod
			f = s
			s = curr
		return s


class Solution:

	def getMax(self, grid, idx):
		return max(grid[0][idx], grid[1][idx])

	def maxSum(self, n, grid):
		f = self.getMax(grid, 0)
		if n == 1:
			return f
		s = max(self.getMax(grid, 1), f)
		for i in range(2, n):
			(s, f) = (max(s, self.getMax(grid, i) + f), s)
		return s


import sys
sys.setrecursionlimit(20000)

class Solution:

	def dfs(self, currState, dp, n, grid):
		if currState >= n:
			return 0
		if dp[currState] != 0:
			return dp[currState]
		dp[currState] = max(max(grid[0][currState], grid[1][currState]) + self.dfs(currState + 2, dp, n, grid), self.dfs(currState + 1, dp, n, grid))
		return dp[currState]

	def maxSum(self, n, grid):
		dp = [0 for i in range(n)]
		return self.dfs(0, dp, n, grid)


class Solution:

	def maxSum(self, N, mat):
		(prev_2, prev_1) = (0, 0)
		prev_2 = max(0, mat[0][0], mat[1][0])
		prev_1 = max(mat[0][1], mat[1][1], prev_2)
		for i in range(2, N):
			(prev_2, prev_1) = (prev_1, max(max(mat[0][i], mat[1][i]) + prev_2, prev_1))
		return prev_1


class Solution:

	def maxSum(self, n, mat):
		if n == 1:
			return max(mat[0][0], mat[0][1])
		dp = [0 for i in range(n)]
		dp[0] = max(mat[0][0], mat[1][0])
		dp[1] = max(mat[0][0], mat[0][1], mat[1][0], mat[1][1])
		for i in range(2, n):
			pick = max(mat[0][i], mat[1][i]) + dp[i - 2]
			notPick = dp[i - 1]
			dp[i] = max(pick, notPick)
		return dp[n - 1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def maxadj(self, co, memo, M, N):
		if co >= N:
			return 0
		if memo[co] != -1:
			return memo[co]
		memo[co] = max(max(M[0][co], M[1][co]) + self.maxadj(co + 2, memo, M, N), self.maxadj(co + 1, memo, M, N))
		return memo[co]

	def maxSum(self, N, mat):
		memo = [-1] * N
		self.maxadj(0, memo, mat, N)
		return memo[0]


class Solution:

	def maxSum(self, N, mat):
		m = []
		for i in range(N):
			m.append(max(mat[1][i], mat[0][i]))
		ans = [0 for i in range(N)]
		ans[0] = m[0]
		ans[1] = max(m[0], m[1])
		for i in range(2, N):
			ans[i] = max(m[i] + ans[i - 2], ans[i - 1])
		return ans[-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def maxSum(self, N, mat):

		def maxSumMat(i, ans, mat, N):
			if i >= N:
				return 0
			if ans[i] != -1:
				return ans[i]
			ans[i] = max(max(mat[0][i], mat[1][i]) + maxSumMat(i + 2, ans, mat, N), maxSumMat(i + 1, ans, mat, N))
			return ans[i]
		ans = [-1] * N
		return maxSumMat(0, ans, mat, N)


class Solution:

	def maxSum(self, N, mat):
		dp = [0] * (N + 2)
		arr = [0 for i in range(N)]
		for i in range(N):
			arr[i] = max(mat[0][i], mat[1][i])
		for i in range(2, N + 2):
			dp[i] = max(dp[i - 1], dp[i - 2] + arr[i - 2])
		return dp[-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		mat = [[0] * N for i in range(2)]
		arr = input().split()
		arr1 = input().split()
		for it in range(N):
			mat[0][it] = int(arr[it])
		for it in range(N):
			mat[1][it] = int(arr1[it])
		ob = Solution()
		print(ob.maxSum(N, mat))


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def recur(self, col, n, mat):
		if col >= n:
			return 0
		if dp[col]:
			return dp[col]
		inc = max(mat[0][col], mat[1][col]) + self.recur(col + 2, n, mat)
		exc = 0 + self.recur(col + 1, n, mat)
		dp[col] = max(inc, exc)
		return dp[col]

	def maxSum(self, N, mat):
		dp = [0] * (N + 1)
		if N == 1:
			return max(mat[0][0], mat[1][0])
		if N == 2:
			return max(mat[0][0], mat[1][0], mat[0][1], mat[1][1])
		dp[1] = max(mat[0][0], mat[1][0])
		dp[2] = max(mat[0][0], mat[1][0], mat[0][1], mat[1][1])
		for i in range(3, N + 1):
			dp[i] = max(dp[i - 1], dp[i - 2] + max(mat[0][i - 1], mat[1][i - 1]))
		return dp[-1]


class Solution:

	def maxSum(self, N, mat):
		f = max(0, mat[0][0], mat[1][0])
		if N == 1:
			return f
		s = max(f, mat[0][1], mat[1][1])
		for i in range(2, N):
			curr = max(max(mat[0][i], mat[1][i]) + f, s)
			f = s
			s = curr
		return s


class Solution:

	def maxSum(self, N, a):
		dp = [[0 for i in range(2)] for i in range(N)]
		dp[0][1] = max(a[0][0], a[1][0])
		for i in range(N):
			dp[i][1] = dp[i - 1][0] + max(a[0][i], a[1][i])
			dp[i][0] = max(dp[i - 1][1], dp[i - 1][0])
		return max(dp[N - 1][1], dp[N - 1][0])


class Solution:

	def maxSum(self, N, mat):
		if N <= 1:
			return max(mat[0][0], mat[1][0])
		mat[0].append(0)
		mat[1].append(0)
		ans = 0
		for j in range(N - 3, -1, -1):
			mxval = 0
			for k in range(2, 4):
				mxval = max(mxval, mat[0][j + k], mat[1][j + k])
			for i in range(2):
				mat[i][j] += mxval
		for j in range(2):
			for i in range(2):
				ans = max(ans, mat[i][j])
		return ans


def helper(nums: list, i: int, m: dict) -> int:
	if i >= len(nums[0]):
		return 0
	if m.get(i):
		return m[i]
	s = max(max(nums[0][i], nums[1][i]) + helper(nums, i + 2, m), helper(nums, i + 1, m))
	m[i] = s
	return s

class Solution:

	def maxSum(self, N, mat):
		(f, s) = (0, 0)
		for i in range(N):
			(f, s) = (s, max(max(mat[0][i], mat[1][i]) + f, s))
		return s


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def recur(self, col, n, mat):
		if col >= n:
			return 0
		if dp[col]:
			return dp[col]
		inc = max(mat[0][col], mat[1][col]) + self.recur(col + 2, n, mat)
		exc = 0 + self.recur(col + 1, n, mat)
		dp[col] = max(inc, exc)
		return dp[col]

	def maxSum(self, N, mat):
		global dp
		dp = [0] * (N + 1)
		return self.recur(0, N, mat)


class Solution:

	def maxSum(self, N, mat):
		if N == 1:
			return max(mat[0][0], mat[1][0])
		else:
			incl = max(mat[0][0], mat[1][0])
			excl = 0
			for i in range(1, N):
				excl_n = max(incl, excl)
				incl = excl + max(mat[0][i], mat[1][i])
				excl = excl_n
			return max(incl, excl)


class Solution:

	def maxSum(self, N, mat):
		arr = []
		for i in range(N):
			arr.append(max(mat[0][i], mat[1][i]))
		dp = [[0 for j in range(2)] for i in range(N)]
		dp[0][1] = arr[0]
		for i in range(1, N):
			dp[i][1] = dp[i - 1][0] + arr[i]
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
		return max(dp[N - 1][0], dp[N - 1][1])


class Solution:

	def maxSum(self, n, A):
		mat = [[0 for j in range(n)] for i in range(2)]
		mat[0][0] = max(A[0][0], A[1][0])
		for j in range(1, n):
			mat[0][j] = max(A[0][j], A[1][j]) + mat[1][j - 1]
			mat[1][j] = max(mat[0][j - 1], mat[1][j - 1])
		return max(mat[0][-1], mat[1][-1])


class Solution:

	def maxSum(self, n, l):
		dp = [0 for _ in range(n + 1)]
		dp[1] = max(l[0][0], l[1][0])
		for i in range(2, n + 1):
			dp[i] = max(dp[i - 1], dp[i - 2] + max(l[0][i - 1], l[1][i - 1]))
		return dp[-1]


class Solution:

	def maxSum(self, N, mat):
		incl = max(mat[0][0], mat[1][0])
		excl = 0
		for i in range(1, N):
			new_excl = max(incl, excl)
			incl = excl + max(mat[0][i], mat[1][i])
			excl = new_excl
		return max(incl, excl)


class Solution:

	def maxSum(self, N, mat):
		grid = mat
		n = N
		incl = max(grid[0][0], grid[1][0])
		excl = 0
		for i in range(1, n):
			excl_new = max(excl, incl)
			incl = excl + max(grid[0][i], grid[1][i])
			excl = excl_new
		return max(excl, incl)


class Solution:

	def maxSum(self, N, mat):
		prev = None
		curr = None
		curr = max(mat[0][0], mat[1][0])
		prev = curr
		curr = max(mat[0][1], mat[1][1])
		curr = max(prev, curr)
		for i in range(2, N):
			temp = curr
			curr = max(prev + max(mat[0][i], mat[1][i]), curr)
			prev = temp
		return curr


class Solution:

	def maxSum(self, N, mat):
		t = [0] * N
		for i in range(N):
			t[i] = max(mat[0][i], mat[1][i])
		if N == 1:
			return t[0]
		elif N == 2:
			return max(t)
		else:
			s = [0] * N
			s[0] = t[0]
			s[1] = t[1]
			s[2] = t[0] + t[2]
			for i in range(3, N):
				s[i] = max(s[i - 2] + t[i], s[i - 3] + t[i])
			return max(s[-1], s[-2])


class Solution:

	def maxSum(self, N, mat):
		i = 0
		return self.solve(N, mat, i)

	def solve(self, N, mat, i):
		f = max(mat[0][0], mat[1][0])
		if N == 0:
			return f
		s = max(f, mat[0][1], mat[1][1])
		if N == 1:
			return s
		for j in range(2, N):
			current = max(s, f + max(mat[0][j], mat[1][j]))
			f = s
			s = current
		return s


class Solution:

	def maxSum(self, N, mat):
		inc = 0
		exl = 0
		for i in range(N):
			new = max(exl, inc)
			inc = exl + max(mat[0][i], mat[1][i])
			exl = new
		return max(inc, exl)


class Solution:

	def maxSum(self, N, mat):
		dp = [0] * N
		prev = 0
		dp[0] = max(mat[0][0], mat[1][0])
		for i in range(1, N):
			dp[i] = max(dp[i - 1], max(mat[0][i], mat[1][i]) + prev)
			prev = dp[i - 1]
		return dp[-1]


class Solution:

	def maxSum(self, n, a):
		if n == 1:
			return max(a[0][0], a[1][0])
		if n == 2:
			return max(a[0][0], a[0][1], a[1][0], a[1][1])
		dp = [0 for i in range(n + 1)]
		dp[1] = max(a[0][0], a[1][0])
		dp[2] = max(a[0][0], a[0][1], a[1][0], a[1][1])
		for i in range(3, n + 1):
			dp[i] = max(dp[i - 1], max(a[0][i - 1], a[1][i - 1]) + dp[i - 2])
		return dp[n]


class Solution:

	def maxSum(self, N, mat):
		x = 0
		y = 0
		for i in range(N):
			z = max(x, y)
			x = y + max(mat[0][i], mat[1][i])
			y = z
		return max(x, y)