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. It is guaranteed that your answer will always fit in the 32-bit integer.
 
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):
		if n < 3:
			m = arr[0]
			for i in range(n):
				m = max(m, arr[i])
			return m
		d = [arr[0], arr[1], arr[2] + arr[0]]
		for i in range(3, n):
			d[i % 3] = max(d[(i - 2) % 3] + arr[i], d[(i - 3) % 3] + arr[i])
		return max(d[(n - 1) % 3], d[(n - 2) % 3], d[(n - 3) % 3])


class Solution:

	def findMaxSum(self, arr, n):
		inc = 0
		ex = 0
		for num in arr:
			newn = ex + num
			ex = max(inc, ex)
			inc = newn
		return max(inc, ex)


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


class Solution:

	def findMaxSum(self, nums, n):
		(rob1, rob2) = (0, 0)
		for i in nums:
			temp = max(rob1 + i, rob2)
			rob1 = rob2
			rob2 = temp
		return rob2


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


import sys
sys.setrecursionlimit(10000000)

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def findMaxSum(self, arr, n):
		max1 = arr[0]
		max2 = 0
		for i in range(1, n):
			x = arr[i]
			if i > 1:
				x += max2
			y = 0 + max1
			curr = max(x, y)
			max2 = max1
			max1 = curr
		return max1


class Solution:

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


class Solution:

	def findMaxSum(self, arr, N):
		if N == 0:
			return 0
		elif N == 1:
			return arr[0]
		else:
			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[N - 1]


class Solution:

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


class Solution:

	def findMaxSum(self, arr, n):
		j = 0
		e = 0
		for i in arr:
			n = max(j, e)
			j = e + i
			e = n
		return max(j, e)


class Solution:

	def findMaxSum(self, arr, n):
		incl = 0
		excl = 0
		for i in arr:
			new_excl = max(excl, incl)
			incl = excl + i
			excl = new_excl
		return max(incl, excl)


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def findMaxSum(self, arr, n):
		if not arr:
			return 0
		incl = 0
		excl = 0
		for i in arr:
			new_excl = excl if excl > incl else incl
			incl = excl + i
			excl = new_excl
		return excl if excl > incl else incl


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def findMaxSum(self, arr, n):
		if n == 1:
			return arr[0]
		if n == 2:
			if arr[1] > arr[0]:
				return arr[1]
			else:
				return arr[0]
		sum2 = arr[2] + arr[0]
		sum0 = arr[0]
		sum1 = arr[1]
		i = 3
		while i < n:
			if sum0 > sum1:
				temp = sum0 + arr[i]
			else:
				temp = arr[i] + sum1
			i += 1
			sum0 = sum1
			sum1 = sum2
			sum2 = temp
		if sum2 > sum1:
			return sum2
		else:
			return sum1


class Solution:

	def findMaxSum(self, arr, n):
		if n == 1:
			return arr[0]
		if n > 2:
			arr[2] += arr[0]
		i = 3
		while i < n:
			if arr[i - 2] > arr[i - 3]:
				arr[i] += arr[i - 2]
			else:
				arr[i] += arr[i - 3]
			i += 1
		if arr[-1] > arr[-2]:
			return arr[-1]
		else:
			return arr[-2]


class Solution:

	def findMaxSum(self, arr, n):
		(x, y) = (0, 0)
		for i in arr:
			temp = max(i + x, y)
			x = y
			y = temp
		return y


class Solution:

	def findMaxSum(self, nums, n):
		if not nums:
			return 0
		if n == 1:
			return nums[0]
		prevOfPrev = nums[0]
		prev = max(nums[0], nums[1])
		for i in range(2, n):
			curr = max((prev, prevOfPrev + nums[i]))
			prevOfPrev = prev
			prev = curr
		return prev


class Solution:

	def findMaxSum(self, arr, n):
		lis = [0, 0, 0]
		for i in range(n):
			sum = max(lis[0], lis[1])
			lis.pop(0)
			lis.append(sum + arr[i])
		return max(lis)


import math

class Solution:

	def findMaxSum(self, arr, n):
		(s1, s2) = (0, 0)
		for i in arr:
			(s1, s2) = (max(s1, s2), max(s1 + i, s2))
		return max(s1, s2)


class Solution:

	def findMaxSum(self, arr, n):
		first = arr[0]
		sum = 0
		for i in range(1, n):
			k = sum + arr[i]
			nsum = max(sum, first)
			first = k
			sum = nsum
		return max(sum, first)

	def gfindMaxSum(self, arr, n):
		odd_start = 0
		even_start = 0
		i = 0
		sum = 0
		while i < n:
			sum += arr[i]
			a = 0
			b = 0
			if i + 2 < n:
				a = arr[i + 2]
			if i + 3 < n:
				b = arr[i + 3]
			if a > b:
				i += 2
			else:
				i += 3
		odd_start = sum
		sum = 0
		i = 1
		while i < n:
			sum += arr[i]
			a = 0
			b = 0
			if i + 2 < n:
				a = arr[i + 2]
			if i + 3 < n:
				b = arr[i + 3]
			if a > b:
				i += 2
			else:
				i += 3
		even_start = sum
		if odd_start >= even_start:
			return odd_start
		else:
			return even_start


class Solution:

	def findMaxSum(self, b, a):
		if a == 1:
			return b[0]
		elif a == 2:
			return max(b[0], b[1])
		else:
			c = []
			c.append(b[0])
			c.append(max(b[1], b[0]))
			for i in range(2, a, 1):
				c.append(max(c[i - 1], b[i] + c[i - 2]))
			return c[a - 1]


class Solution:

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


class Solution:

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


class Solution:

	def findMaxSum(self, arr, n):
		if n < 3:
			return max(arr)
		i = arr[0]
		ni = 0
		for j in range(1, n):
			temp = ni
			ni = max(i, ni)
			i = temp + arr[j]
		return max(i, ni)


class Solution:

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