Given an array Arr of size N containing positive integers. Find the maximum sum of a subsequence such that no two numbers in the sequence should be adjacent in the array. 
Example 1:
Input:
N = 6
Arr[] = {5, 5, 10, 100, 10, 5}
Output: 110
Explanation: If you take indices 0, 3
and 5, then Arr[0]+Arr[3]+Arr[5] =
5+100+5 = 110.
Example 2:
Input:
N = 4
Arr[] = {3, 2, 7, 10}
Output: 13
Explanation: 3 and 10 forms a non
continuous  subsequence with maximum
sum.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMaxSum() which takes the array of integers arr and n as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ Arr_{i} ≤ 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:

	

	def findMaxSum(self,arr, n):

		# code here

Solutions:
class Solution:

	def findMaxSum(self, arr, n):
		prev1 = arr[0]
		prev2 = 0
		for ind in range(1, n):
			pick = arr[ind]
			if ind - 2 >= 0:
				pick += prev2
			notpick = prev1
			prev2 = prev1
			prev1 = max(pick, notpick)
		return prev1


class Solution:

	def findMaxSum(self, arr, n):
		dp = [-1 for i in range(n)]
		dp[0] = arr[0]
		for ind in range(1, n):
			pick = arr[ind]
			if ind - 2 >= 0:
				pick += dp[ind - 2]
			notpick = dp[ind - 1]
			dp[ind] = max(pick, notpick)
		return dp[n - 1]


class Solution:

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


class Solution:

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


class Solution:

	def findMaxSum(self, arr, n):
		(prev2, prev1) = (0, arr[0])
		for i in range(1, n):
			not_pick = prev1
			pick = arr[i] + prev2
			prev2 = prev1
			prev1 = max(not_pick, pick)
		return prev1


class Solution:

	def findMaxSum(self, arr, n):
		left = arr[0]
		if n == 1:
			return left
		right = max(arr[0], arr[1])
		for i in range(2, n):
			valone = left + arr[i]
			left = right
			if valone > right:
				right = valone
		return right


class Solution:

	def findMaxSum(self, arr, n):
		include = arr[0]
		exclude = 0
		newinclude = 0
		for i in range(1, n):
			current = arr[i]
			newinclude = exclude + current
			newexclude = max(include, exclude)
			include = newinclude
			exclude = newexclude
		return max(exclude, include)


class Solution:

	def findMaxSum(self, arr, n):
		if len(arr) == 1:
			return arr[0]
		exc = 0
		inc = arr[0]
		for i in range(1, n):
			new_inc = exc + arr[i]
			new_exc = max(inc, exc)
			inc = new_inc
			exc = new_exc
		return max(new_inc, new_exc)


class Solution:

	def findMaxSum(self, arr, n):
		inc = arr[0]
		exclu = 0
		newinc = 0
		newexclu = 0
		for i in range(1, n):
			newinc = exclu + arr[i]
			newexclu = max(inc, exclu)
			inc = newinc
			exclu = newexclu
		return max(inc, exclu)


class Solution:

	def findMaxSum(self, arr, n):
		dp = [-1] * (n + 1)
		dp[0] = arr[0]
		for ind in range(1, n):
			left = arr[ind]
			if ind > 1:
				left += dp[ind - 2]
			right = 0 + dp[ind - 1]
			dp[ind] = max(left, right)
		return dp[n - 1]


class Solution:

	def maxSum(self, index, arr, dp):
		if index == 0:
			return arr[index]
		if dp[index] != -1:
			return dp[index]
		notTake = 0 + self.maxSum(index - 1, arr, dp)
		take = arr[index]
		if index > 1:
			take = arr[index] + self.maxSum(index - 2, arr, dp)
		dp[index] = max(notTake, take)
		return max(notTake, take)

	def findMaxSum(self, arr, n):
		table = [0 for i in range(n)]
		table[0] = arr[0]
		for index in range(1, n):
			notTake = table[index - 1]
			take = arr[index]
			if index > 1:
				take = arr[index] + table[index - 2]
			table[index] = max(take, notTake)
		return table[n - 1]


class Solution:

	def findMaxSum(self, arr, n):
		prev2 = 0
		prev1 = arr[0]
		for i in range(1, n):
			inc = prev2 + arr[i]
			exl = prev1 + 0
			ans = max(inc, exl)
			prev2 = prev1
			prev1 = ans
		return prev1


class Solution:

	def findMaxSum(self, arr, n):
		dp = [0] * n
		dp[0] = arr[0]
		for i in range(1, n):
			inc = dp[i - 2] + arr[i]
			exl = dp[i - 1] + 0
			dp[i] = max(inc, exl)
		return dp[n - 1]


class Solution:

	def findMaxSum(self, arr, n):

		def recursive(ind):
			if ind >= n:
				return 0
			dp[0] = arr[0]
			for ind in range(1, n):
				pick = arr[ind] + dp[ind - 2]
				non_pick = dp[ind - 1]
				dp[ind] = max(pick, non_pick)
			return dp[ind]
		dp = [0 for i in range(n + 3)]
		return recursive(0)


class Solution:

	def solve(self, a, n, dp):
		if dp[n] != -1:
			return dp[n]
		if n < 0:
			return 0
		if n == 0:
			return a[0]
		inc = self.solve(a, n - 2, dp) + a[n]
		exc = self.solve(a, n - 1, dp)
		dp[n] = max(inc, exc)
		return dp[n]

	def solve1(self, a, n, dp):
		dp[0] = a[0]
		for i in range(1, n):
			inc = dp[i - 2] + a[i]
			exc = dp[i - 1]
			dp[i] = max(inc, exc)
		return dp[n - 1]

	def findMaxSum(self, arr, n):
		dp = [0 for _ in range(n)]
		return self.solve1(arr, n, dp)


class Solution:

	def findMaxSum(self, arr, n):
		dp = [-1] * n
		dp[0] = arr[0]
		for i in range(n):
			p = arr[i]
			if i > 1:
				p += dp[i - 2]
			np = 0 + dp[i - 1]
			dp[i] = max(p, np)
		return dp[n - 1]


class Solution:

	def findMaxSum(self, arr, n):
		prev1 = arr[0]
		prev2 = 0
		curr = 0
		for i in range(1, n):
			pick = arr[i]
			if i > 1:
				pick = pick + prev2
			npick = 0 + prev1
			curr = max(pick, npick)
			prev2 = prev1
			prev1 = curr
		return prev1


import sys
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7

class Solution:

	def findMaxSum(self, arr, N):
		dp = [[0 for i in range(2)] for j in range(N)]
		if N == 1:
			return arr[0]
		dp[0][0] = 0
		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][1], dp[i - 1][0])
		return max(dp[N - 1][0], dp[N - 1][1])


class Solution:

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

	def rec(self, i, arr, dp):
		if i < 0:
			return 0
		if dp[i] != -1:
			return dp[i]
		take = self.rec(i - 2, arr, dp) + arr[i]
		noTake = self.rec(i - 1, arr, dp) + 0
		dp[i] = max(take, noTake)
		return max(take, noTake)


class Solution:

	def findMaxSum(self, nums, n):
		dp1 = 0
		dp2 = 0
		for i in range(len(nums)):
			(dp1, dp2) = (dp2, max(dp2, nums[i] + dp1))
		return dp2


class Solution:

	def findMaxSum(self, arr, n):
		import sys
		sys.setrecursionlimit(10 ** 9)
		dp = [-1] * n
		return self.solve(n - 1, arr, dp)

	def solve(self, ind, arr, dp):
		if ind == 0:
			return arr[ind]
		if ind < 0:
			return 0
		if dp[ind] != -1:
			return dp[ind]
		pick = arr[ind] + self.solve(ind - 2, arr, dp)
		npick = 0 + self.solve(ind - 1, arr, dp)
		dp[ind] = max(pick, npick)
		return dp[ind]


class Solution:

	def findMaxSum(self, a, n):
		if n == 1:
			return a[0]
		rob1 = a[0]
		rob2 = max(a[0], a[1])
		for i in a[2:]:
			(rob1, rob2) = (rob2, max(i + rob1, rob2))
		return rob2


class Solution:

	def util(self, arr, n, dp):
		if n == 0:
			return arr[0]
		if n < 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		incl = self.util(arr, n - 2, dp) + arr[n]
		excl = self.util(arr, n - 1, dp)
		dp[n] = max(incl, excl)
		return dp[n]

	def utiltab(self, arr, n):
		dp = [0] * n
		dp[0] = arr[0]
		for i in range(1, n):
			incl = dp[i - 2] + arr[i]
			excl = dp[i - 1]
			dp[i] = max(incl, excl)
		return dp[n - 1]

	def findMaxSum(self, arr, n):
		dp = [-1] * (n + 1)
		ans = self.utiltab(arr, n)
		return ans


class Solution:

	def findMaxSum(self, arr, n):
		dp = [-1] * n
		prev = arr[0]
		prev2 = 0
		for i in range(1, n):
			take = arr[i]
			if i > 1:
				take += prev2
			not_take = prev
			curri = max(take, not_take)
			prev2 = prev
			prev = curri
		return prev


import sys
sys.setrecursionlimit(100000)

class Solution:

	def findMaxSum(self, arr, n):
		if n == 1:
			return arr[0]
		dp = [0] * n
		dp[0] = arr[0]
		dp[1] = max(arr[0], arr[1])
		for i in range(2, n):
			dp[i] = max(dp[i - 2] + arr[i], dp[i - 1])
		return dp[-1]


class Solution:

	def findMaxSum(self, arr, n):
		if n == 1:
			return arr[0]
		first = arr[0]
		second = max(arr[0], arr[1])
		for i in range(2, n):
			(first, second) = (second, max(arr[i] + first, second))
		return second


class Solution:

	def findMaxSum(self, arr, n):
		inc = 0
		exc = 0
		for i in arr:
			new_exc = max(inc, exc)
			inc = i + exc
			exc = new_exc
		return max(inc, exc)


class Solution:

	def findMaxSum(self, arr, n):
		prev = arr[0]
		prev2 = 0
		for i in range(1, n):
			take = arr[i]
			if i > 1:
				take += prev2
			nontake = prev
			curr = max(take, nontake)
			prev2 = prev
			prev = curr
		return prev


import sys
sys.setrecursionlimit(10000000)

class Solution:

	def solve(self, arr, index, n, dp):
		if index >= n:
			return 0
		if dp[index] != -1:
			return dp[index]
		incl = self.solve(arr, index + 2, n, dp)
		ans = incl + arr[index]
		excl = self.solve(arr, index + 1, n, dp)
		dp[index] = max(ans, excl)
		return dp[index]

	def findMaxSum(self, arr, n):
		index = 0
		dp = [-1 for i in range(n + 1)]
		ans = self.solve(arr, index, n, dp)
		return ans


class Solution:

	def findMaxSum(self, arr, n):
		(self.arr, self.n) = (arr, n)
		aux = [0] * (n + 2)
		for i in range(n + 1, -1, -1):
			if i >= n:
				aux[i] = 0
			else:
				count1 = arr[i] + aux[i + 2]
				count2 = aux[i + 1]
				aux[i] = max(count1, count2)
		return aux[0]

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


class Solution:

	def findMaxSum(self, arr, n):
		if len(arr) == 1:
			return arr[0]
		if len(arr) == 2:
			if arr[0] > arr[1]:
				return arr[0]
			else:
				return arr[1]

		def fun(arr):
			dp = [0 for _ in range(len(arr) + 1)]
			dp[0] = arr[0]
			if arr[0] > arr[1]:
				dp[1] = arr[0]
			else:
				dp[1] = arr[1]
			for i in range(2, len(arr)):
				dp[i] = max(arr[i] + dp[i - 2], dp[i - 1])
			return dp[i]
		return fun(arr)


class Solution:

	def findMaxSum(self, arr, n):
		return self.MaxSum(arr, n)

	def MaxSum(self, arr, n):
		dp = [-1] * n
		dp[0] = arr[0]
		for i in range(len(arr)):
			pick = arr[i]
			if i > 1:
				pick += dp[i - 2]
			nonpick = dp[i - 1]
			dp[i] = max(pick, nonpick)
		return dp[i]


class Solution:

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


class Solution:

	def findMaxSum(self, arr, n):
		li = []
		for i in range(0, n):
			li.append(0)
		if n == 0:
			return 0
		if n == 1:
			return arr[0]
		li[0] = arr[0]
		li[1] = arr[1]
		for i in range(2, n):
			li[i] = max(li[i - 3], li[i - 2]) + arr[i]
		return max(li)


import sys
sys.setrecursionlimit(150000)

class Solution:

	def findMaxSum(self, arr, n):
		dp = [-1] * (n + 1)
		dp[0] = arr[0]
		for idx in range(1, n):
			pick = arr[idx]
			if idx > 1:
				pick += dp[idx - 2]
			notPick = dp[idx - 1]
			dp[idx] = max(pick, notPick)
		return dp[n - 1]


class Solution:

	def findMaxSum(self, arr, n):
		prev = arr[0]
		prev2 = 0
		for i in range(1, n):
			pick = arr[i]
			if i > 1:
				pick += prev2
			not_pick = 0 + prev
			curr = max(pick, not_pick)
			prev2 = prev
			prev = curr
		return prev


class Solution:

	def findMaxSum(self, arr, n):
		(ans, mx) = (0, 0)
		for i in range(n):
			val = arr[i] + mx
			mx = max(mx, ans)
			ans = max(ans, val)
		return ans


class Solution:

	def findMaxSum(self, arr, n):
		memo = {}
		return self.sp_tab_find_max_sum(0, arr, n - 1)

	def find_max_sum(self, curr_index, arr, last_index, memo):
		if curr_index > last_index:
			return 0
		if curr_index == last_index:
			return arr[last_index]
		curr_key = curr_index
		if memo.get(curr_key) != None:
			return memo.get(curr_key)
		consider = self.find_max_sum(curr_index + 2, arr, last_index, memo) + arr[curr_index]
		not_consider = self.find_max_sum(curr_index + 1, arr, last_index, memo)
		memo[curr_key] = max(consider, not_consider)
		return memo.get(curr_key)

	def tab_find_max_sum(self, first_index, arr, last_index, memo):
		memo[last_index] = arr[last_index]
		for curr_index in range(last_index - 1, first_index - 1, -1):
			consider = arr[curr_index]
			not_consider = 0
			if curr_index + 2 <= last_index:
				consider += memo[curr_index + 2]
			if curr_index + 1 <= last_index:
				not_consider += memo[curr_index + 1]
			memo[curr_index] = max(consider, not_consider)
		return memo.get(first_index)

	def sp_tab_find_max_sum(self, first_index, arr, last_index):
		next_val = arr[last_index]
		next2_val = 0
		for curr_index in range(last_index - 1, first_index - 1, -1):
			consider = arr[curr_index]
			not_consider = 0
			if curr_index + 2 <= last_index:
				consider += next2_val
			if curr_index + 1 <= last_index:
				not_consider += next_val
			curr_val = max(consider, not_consider)
			next2_val = next_val
			next_val = curr_val
		return next_val


from math import inf

class Solution:

	def findMaxSum(self, arr, n):
		if n == 1:
			return arr[0]
		prev2 = arr[-1]
		prev1 = max(arr[-2], prev2)
		for i in range(n - 3, -1, -1):
			pick = arr[i] + prev2
			no_pick = 0 + prev1
			prev2 = prev1
			prev1 = max(pick, no_pick)
		return prev1


class Solution:

	def findMaxSum(self, arr, n):
		prev = 0
		cur = 0
		next = arr[0]
		for i in range(1, n):
			x = next
			next = max(arr[i], arr[i] + cur, arr[i] + prev)
			y = cur
			cur = x
			prev = y
		return max(prev, cur, next)


class Solution:

	def findMaxSum(self, arr, n):
		a = arr[n - 1]
		b = max(arr[n - 1], arr[n - 2])
		for i in range(n - 3, -1, -1):
			if arr[i] + a > b:
				temp = a
				a = b
				b = arr[i] + temp
			else:
				a = b
		return b


class Solution:
	dp = [-1] * 1000000

	def gen(self, arr, n, count):
		if count > n:
			return 0
		if self.dp[count] != -1:
			return self.dp[count]
		l = self.gen(arr, n, count + 2) + arr[count]
		r = self.gen(arr, n, count + 1)
		self.dp[count] = max(l, r)
		return self.dp[count]

	def findMaxSum(self, arr, n):
		dp = [-1] * n
		dp[n - 1] = arr[n - 1]
		dp[n - 2] = max(arr[n - 1], arr[n - 2])
		for i in range(n - 3, -1, -1):
			if arr[i] + dp[i + 2] > dp[i + 1]:
				dp[i] = arr[i] + dp[i + 2]
			else:
				dp[i] = dp[i + 1]
		return dp[0]


class Solution:

	def findMaxSum(self, arr, n):
		dp = [0] * n
		dp[0] = arr[0]
		for i in range(1, n):
			two = arr[i]
			if i > 1:
				two += dp[i - 2]
			one = dp[i - 1]
			dp[i] = max(two, one)
		return dp[-1]


class Solution:

	def findMaxSum(self, arr, n):
		(pre1, pre2) = (arr[0], 0)
		mx = 0
		for i in range(1, n):
			take = arr[i] + pre2
			notake = 0 + pre1
			mx = max(take, notake)
			pre2 = pre1
			pre1 = mx
		return pre1


class Solution:

	def findMaxSum(self, arr, n):
		import sys
		sys.setrecursionlimit(100000000)
		if n == 1:
			return arr[0]
		dp = [-1] * (n + 1)
		dp[0] = arr[0]
		for i in range(1, n):
			pick = arr[i] + (dp[i - 2] if i > 1 else 0)
			notpick = 0 + dp[i - 1]
			dp[i] = max(pick, notpick)
		return dp[n - 1]


class Solution:

	def findMaxSum(self, arr, n):
		import sys
		sys.setrecursionlimit(100000000)
		if n == 1:
			return arr[0]
		dp = [-1] * (n + 1)
		self.Util(arr, n - 1, dp)
		return dp[n - 1]

	def Util(self, arr, ind, dp):
		if ind == 0:
			return arr[ind]
		if ind < 0:
			return 0
		if dp[ind] != -1:
			return dp[ind]
		pick = arr[ind] + self.Util(arr, ind - 2, dp)
		notpick = 0 + self.Util(arr, ind - 1, dp)
		dp[ind] = max(pick, notpick)
		return dp[ind]


class Solution:

	def findMaxSum(self, arr, n):
		prev = arr[0]
		prev2 = 0
		for i in range(1, n):
			temp = prev
			sum = max(prev2 + arr[i], prev)
			prev = sum
			prev2 = temp
		return prev


class Solution:

	def findMaxSum(self, arr, n):
		if n == 0:
			return 0
		value1 = arr[0]
		if n == 1:
			return value1
		value2 = max(arr[0], arr[1])
		if n == 2:
			return value2
		for i in range(2, n):
			max_sum = max(arr[i] + value1, value2)
			value1 = value2
			value2 = max_sum
		return max_sum


class Solution:

	def findMaxSum(self, arr, n):
		dp = [-1 for _ in range(n)]
		prev = arr[0]
		prev2 = 0
		for ind in range(1, n):
			if ind > 1:
				pick = arr[ind] + prev2
			else:
				pick = arr[ind]
			notpick = 0 + prev
			curri = max(pick, notpick)
			prev2 = prev
			prev = curri
		return prev


class Solution:

	def findMaxSum(self, arr, n):

		def calc(n):
			prev = arr[0]
			prev1 = 0
			for i in range(1, n):
				pick = arr[i]
				if i > 1:
					pick += prev1
				npick = 0 + prev
				cur = max(pick, npick)
				prev1 = prev
				prev = cur
			return prev
		return calc(n)


class Solution:

	def findMaxSum(self, arr, n):

		def calc(n):
			dp = [-1] * n
			dp[0] = arr[0]
			for i in range(1, n):
				pick = arr[i]
				if i > 1:
					pick += dp[i - 2]
				npick = 0 + dp[i - 1]
				dp[i] = max(pick, npick)
			return dp[n - 1]
		return calc(n)


class Solution:

	def findMaxSum(self, arr, n):
		dp = [0] * n
		dp[0] = arr[0]
		for i in range(1, len(arr)):
			include = dp[i - 2] + arr[i]
			exclude = dp[i - 1]
			dp[i] = max(include, exclude)
		return dp[n - 1]


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def findMaxSum(self, arr, n):
		if n == 1:
			return arr[0]
		prev2 = arr[0]
		prev1 = max(arr[0], arr[1])
		for i in range(2, n):
			p = prev2 + arr[i]
			np = prev1
			curr = max(p, np)
			prev2 = prev1
			prev1 = curr
		return prev1


class Solution:

	def findMaxSum(self, arr, n):
		if len(arr) > 2:
			arr[2] += arr[0]
			for i in range(3, n):
				arr[i] += max(arr[i - 2], arr[i - 3])
		return max(arr)


class Solution:

	def findMaxSum(self, nums, n):
		prev = nums[0]
		prev2 = 0
		for i in range(1, n):
			take = nums[i]
			if i > 1:
				take += prev2
			nottake = prev
			curr = max(take, nottake)
			prev2 = prev
			prev = curr
		return prev