Given an array Arr of size N containing positive integers. Find the maximum sum that can be formed which has no three consecutive elements present.
Example 1:
Input: arr[] = {1,2,3}
Output: 5
Explanation: All three element present in the array is
consecutive, hence we have to consider just two
element sum having maximum,which is 2+3 = 5
Example 2:
Input: arr[] = {3000,2000,1000,3,10}
Output: 5013
Explanation: 3000 + 2000 + 3 + 10 = 5013.
Here no three elements is consecutive in that subsequence.
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(N)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ Arr_{i} ≤ 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3





class Solution:

	

	def findMaxSum(self,arr, n):

		# code here

Solutions:
class Solution:

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


class Solution:

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


class Solution:

	def rec_sol(self, arr, n):
		if n == 0:
			return 0
		if n == 1:
			return arr[0]
		if n == 2:
			return arr[0] + arr[1]
		if n == 3:
			return max(max(arr[1] + arr[0], arr[1] + arr[2]), arr[0] + arr[2])
		return max(max(arr[n - 1] + arr[n - 2] + self.rec_sol(arr, n - 3), arr[n - 2] + arr[n - 3] + self.rec_sol(arr, n - 4)), arr[n - 1] + self.rec_sol(arr, n - 2))

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

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def findMaxSum(self, arr, n):
		dp = [0, 0, 0]
		for i in arr:
			third = max(dp)
			sec = dp[0] + i
			first = dp[2] + i
			(dp[0], dp[1], dp[2]) = (first, sec, third)
		return max(dp)


class Solution:

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


class Solution:

	def solve(self, arr, n):
		dp = [-1 for _ in range(n)]
		dp[0] = arr[0]
		dp[1] = arr[0] + arr[1]
		dp[2] = max(arr[0] + arr[1], arr[0] + arr[2], arr[1] + arr[2])
		if n > 3:
			for i in range(3, n):
				exclude_first_num = dp[i - 1]
				exclude_second_num = arr[i] + dp[i - 2]
				exclude_third_num = arr[i] + arr[i - 1] + dp[i - 3]
				dp[i] = max(exclude_first_num, exclude_second_num, exclude_third_num)
		return dp[n - 1]

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


class Solution:

	def findMaxSum(self, arr, n):
		k = 3
		memm = [[0 for c in range(n)] for r in range(k)]
		for r in range(1, k):
			memm[r][0] = arr[0]
		for c in range(1, n):
			memm[0][c] = memm[k - 1][c - 1]
			for r in range(1, k):
				memm[r][c] = max(memm[r - 1][c - 1] + arr[c], memm[k - 1][c - 1])
		return memm[k - 1][n - 1]


import sys
sys.setrecursionlimit(10 ** 9)

def util(arr, n, k, memm, allowed):
	if n < 0:
		return 0
	if memm[k][n] != -1:
		return memm[k][n]
	if k == 0:
		return util(arr, n - 1, allowed, memm, allowed)
	ans = 0
	ans = max(ans, util(arr, n - 1, k - 1, memm, allowed) + arr[n])
	ans = max(ans, util(arr, n - 1, allowed, memm, allowed))
	memm[k][n] = ans
	return ans

class Solution:

	def findMaxSum(self, arr, n):
		k = 3
		memm = [[0 for c in range(n)] for r in range(k)]
		for r in range(1, k):
			memm[r][0] = arr[0]
		for c in range(1, n):
			memm[0][c] = memm[k - 1][c - 1]
			for r in range(1, k):
				memm[r][c] = max(memm[r - 1][c - 1] + arr[c], memm[k - 1][c - 1])
		return memm[k - 1][n - 1]


class Solution:

	def findMaxSum(self, a, n):
		prev3 = a[0]
		prev2 = a[0] + a[1]
		prev1 = max(a[0] + a[1], a[1] + a[2], a[0] + a[2])
		for i in range(3, n):
			incl1 = a[i] + prev2
			incl2 = a[i] + a[i - 1] + prev3
			excl = prev1
			ans = max(incl1, incl2, excl)
			prev3 = prev2
			prev2 = prev1
			prev1 = ans
		return prev1


class Solution:

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


class Solution:

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


class Solution:

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


def solve(arr, n, idx, dp):
	if idx >= n:
		return 0
	if dp[idx] != -1:
		return dp[idx]
	inc = arr[idx] + solve(arr, n, idx + 2, dp)
	exc = solve(arr, n, idx + 1, dp)
	dp[idx] = max(inc, exc)
	return dp[idx]

class Solution:

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


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def solve(self, arr, n, dp):
		if n == 0:
			return arr[0]
		if n <= 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		opt1 = self.solve(arr, n - 1, dp)
		opt2 = arr[n] + self.solve(arr, n - 2, dp)
		opt3 = arr[n] + arr[n - 1] + self.solve(arr, n - 3, dp)
		dp[n] = max(opt1, opt2, opt3)
		return dp[n]

	def tabular(self, arr, n):
		dp = [0 for i in range(n + 1)]
		(p1, p2, p3) = (arr[0], 0, 0)
		for i in range(1, n):
			opt2 = opt3 = 0
			opt1 = p1
			opt2 = arr[i] + p2
			opt3 = arr[i] + arr[i - 1] + p3
			p3 = p2
			p2 = p1
			p1 = max(opt1, opt2, opt3)
		return p1

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


class Solution:

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


import sys

class Solution:

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


class Solution:
	dp = [-1] * 10000000

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

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


class Solution:

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


class Solution:

	def recSol(self, arr, i, dp):
		n = len(arr)
		if i >= n:
			return 0
		if dp[i] != -1:
			return dp[i]
		res1 = arr[i] + self.recSol(arr, i + 2, dp)
		res2 = 0
		if i + 1 < n:
			res2 = arr[i] + arr[i + 1] + self.recSol(arr, i + 3, dp)
		res3 = self.recSol(arr, i + 1, dp)
		dp[i] = max(res1, res2, res3)
		return dp[i]

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


class Solution:

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


class Solution:

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


class Solution:

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