Stickler the thief wants to loot money from a society having n houses in a single line. He is a weird person and follows a certain rule when looting the houses. According to the rule, he will never loot two consecutive houses. At the same time, he wants to maximize the amount he loots. The thief knows which house has what amount of money but is unable to come up with an optimal looting strategy. He asks for your help to find the maximum money he can get if he strictly follows the rule. Each house has a[i]amount of money present in it.
Example 1:
Input:
n = 6
a[] = {5,5,10,100,10,5}
Output: 110
Explanation: 5+100+5=110
Example 2:
Input:
n = 3
a[] = {1,2,3}
Output: 4
Explanation: 1+3=4
Your Task:
Complete the functionFindMaxSum()which takes an array arr[] and n as input which returns the maximum money he can get following the rules
Expected Time Complexity:O(N).
Expected Space Complexity:O(N).
Constraints:
1 ≤ n ≤ 10^{4}
1 ≤ a[i] ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:  

    

    #Function to find the maximum money the thief can get.

    def FindMaxSum(self,a, n):

        

        # code here

Solutions:
class Solution:

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


from sys import maxsize

class Solution:

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


class Solution:

	def FindMaxSum(self, a, n):
		if n == 1:
			return a[0]
		if n == 2:
			return max(a[0], a[1])
		d = [a[0], a[1], a[0] + a[2]]
		for i in range(3, n):
			d.append(max(d[len(d) - 2] + a[i], d[len(d) - 3] + a[i]))
		return max(d[len(d) - 1], d[len(d) - 2])


class Solution:

	def FindMaxSum(self, a, n):
		if n == 1:
			return a[0]
		prevMax = a[0]
		currMax = max(a[0], a[1])
		prev = a[1]
		for i in range(2, n):
			curr = a[i] + prevMax
			prevMax = max(prevMax, prev)
			currMax = max(currMax, curr)
			prev = curr
		return currMax


class Solution:

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


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, a, n):
		dp = [0 for _ in range(n + 1)]
		dp[1] = a[0]
		for j in range(2, n + 1):
			dp[j] = max(a[j - 1] + dp[j - 2], dp[j - 1])
		return dp[n]


class Solution:

	def FindMaxSum(self, arr, n):
		if n == 0:
			return 0
		elif n == 1:
			return arr[0]
		elif n == 2:
			return max(arr[0], arr[1])
		ele1 = arr[0]
		ele2 = max(ele1, arr[1])
		sum1 = 0
		for i in range(2, n):
			sum1 = max(arr[i] + ele1, ele2)
			ele1 = ele2
			ele2 = sum1
		return sum1


class Solution:

	def FindMaxSum(self, a, n):
		s = 0
		t = 0
		for i in a:
			t2 = max(t, s)
			s = t + i
			t = t2
		return max(t, s)


class Solution:

	def FindMaxSum(self, arr, n):
		a = arr[0]
		ex = 0
		for i in range(1, n):
			nex = max(a, ex)
			a = ex + arr[i]
			ex = nex
		return max(a, ex)


class Solution:

	def FindMaxSum(self, a, n):
		if len(a) == 0:
			return 0
		if len(a) == 1:
			return a[0]
		table = [0 for x in range(n)]
		table[0] = a[0]
		table[1] = max(a[0], a[1])
		for i in range(2, n):
			table[i] = max(table[i - 1], table[i - 2] + a[i])
		return table[n - 1]


class Solution:

	def FindMaxSum(self, a, n):
		arr = a
		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, a, n):
		(prev2, prev1) = (0, a[0])
		for i in range(1, n):
			not_pick = prev1
			pick = a[i] + prev2
			prev2 = prev1
			prev1 = max(not_pick, pick)
		return prev1


class Solution:

	def FindMaxSum(self, a, n):
		if n == 1:
			return a[0]
		elif n == 2:
			return max(a)
		r = [a[0], a[1], a[0] + a[2]]
		for i in range(3, n):
			r.append(a[i] + max(r[i - 2], r[i - 3]))
		return max(r)


class Solution:

	def FindMaxSum(self, a, n):
		nums = a
		r1 = 0
		r2 = 0
		for i in range(len(nums)):
			temp = max(r1 + nums[i], r2)
			r1 = r2
			r2 = temp
		return r2


class Solution:

	def FindMaxSum(self, a, n):
		if len(a) == 1:
			return a[0]
		prevprev = a[0]
		prev = max(a[1], a[0])
		for i in range(2, n):
			curr = max(prev, prevprev + a[i])
			prevprev = prev
			prev = curr
		return prev


class Solution:

	def FindMaxSum(self, a, n):
		dp = [-1] * n

		def recHelper(k):
			if k == 0:
				return a[0]
			if k == 1:
				return max(a[0], a[1])
			if dp[k] != -1:
				return dp[k]
			dp[k] = max(recHelper(k - 1), a[k] + recHelper(k - 2))
			return dp[k]
		return recHelper(n - 1)


class Solution:

	def FindMaxSum(self, a, n):
		incl = 0
		excl = 0
		for i in range(n):
			curr = max(a[i] + excl, incl)
			excl = incl
			incl = curr
		return curr


class Solution:

	def FindMaxSum(self, a, n):
		lastElementInclude = a[0]
		lastElementExclude = 0
		for x in a[1:]:
			temp = lastElementInclude
			lastElementInclude = max(lastElementExclude + x, lastElementInclude)
			lastElementExclude = temp
		return max(lastElementInclude, lastElementExclude)


class Solution:

	def FindMaxSum(self, a, n):
		include = a[0]
		exclude = 0
		for x in a[1:]:
			temp = include
			include = max(exclude + x, include)
			exclude = temp
		return max(include, exclude)


class Solution:

	def FindMaxSum(self, a, n):
		if n == 0:
			return 0
		if n == 1:
			return a[0]
		if n == 2:
			return max(a[0], a[1])
		prev2 = 0
		prev1 = a[0]
		for i in range(1, n):
			ans = max(a[i] + prev2, prev1)
			prev2 = prev1
			prev1 = ans
		return prev1


class Solution:

	def FindMaxSum(self, a, n):
		(rob1, rob2) = (0, 0)
		for n in a:
			temp = max(n + rob1, rob2)
			rob1 = rob2
			rob2 = temp
		return rob2


class Solution:

	def FindMaxSum(self, nums, n):
		f = 0
		s = 0
		x = 0
		l = len(nums)
		for i in range(0, l):
			x = max(nums[i] + f, s)
			f = s
			s = x
		return x


class Solution:

	def solve(self, idx, a, n):
		if idx >= n:
			return 0
		incl = a[idx] + self.solve(idx + 2, a, n)
		excl = self.solve(idx + 1, a, n)
		return max(incl, excl)

	def solve_memo(self, idx, a, n, F):
		if idx >= n:
			return 0
		if F[idx] != -1:
			return F[idx]
		incl = a[idx] + self.solve_memo(idx + 2, a, n, F)
		excl = self.solve_memo(idx + 1, a, n, F)
		F[idx] = max(incl, excl)
		return F[idx]

	def solve_tab(self, a, n):
		F = [0 for _ in range(n + 2)]
		for idx in range(n - 1, -1, -1):
			incl = a[idx] + F[idx + 2]
			excl = F[idx + 1]
			F[idx] = max(incl, excl)
		return F[0]

	def solve_opt(self, a, n):
		prev2 = prev1 = 0
		for idx in range(n - 1, -1, -1):
			incl = a[idx] + prev2
			excl = prev1
			ans = max(incl, excl)
			prev2 = prev1
			prev1 = ans
		return prev1

	def FindMaxSum(self, a, n):
		return self.solve_opt(a, n)


class Solution:

	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, a, n):
		dp = [0 for _ in range(n)]
		return self.solve1(a, n, dp)


class Solution:

	def FindMaxSum(self, a, n):
		if n == 1:
			return 0 if a[0] < 0 else a[0]
		include = [0] * len(a)
		exclude = [0] * len(a)
		(include[0], include[1]) = (a[0], a[1])
		if include[0] < 0:
			include[0] = 0
		(exclude[0], exclude[1]) = (0, include[0])
		if a[1] < 0:
			include[1] = 0
		for j in range(2, len(a), 1):
			inc = max(exclude[j - 2], include[j - 2])
			exc = max(include[j - 1], exclude[j - 1])
			if a[j] < 0:
				(include[j], exclude[j]) = (exc, exc)
			else:
				(include[j], exclude[j]) = (inc + a[j], exc)
		return max(include[-1], exclude[-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


class Solution:

	def FindMaxSum(self, arr, N):

		def solveUtil(ind, arr, dp):
			if dp[ind] != -1:
				return dp[ind]
			if ind == 0:
				return arr[ind]
			if ind < 0:
				return 0
			pick = arr[ind] + solveUtil(ind - 2, arr, dp)
			nonPick = 0 + solveUtil(ind - 1, arr, dp)
			dp[ind] = max(pick, nonPick)
			return dp[ind]
		dp = [-1 for i in range(n)]
		return solveUtil(n - 1, arr, dp)


class Solution:

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

	def FindMaxSum(self, a, n):
		prev = 0
		prev_2 = 0
		current = 0
		for i in range(n - 1, -1, -1):
			current = max(a[i] + prev_2, 0 + prev)
			prev_2 = prev
			prev = current
		return prev


class Solution:

	def FindMaxSum(self, a, n):

		def find_max(a, i, dp):
			if i >= len(a):
				return 0
			if dp[i] != -1:
				return dp[i]
			c = a[i] + find_max(a, i + 2, dp)
			b = find_max(a, i + 1, dp)
			dp[i] = max(c, b)
			return dp[i]
		dp = [-1] * n
		return find_max(a, 0, dp)


class Solution:

	def solve(self, n, arr, memo):
		if n == 0:
			return arr[n]
		if n < 0:
			return 0
		if memo[n] != -1:
			return memo[n]
		take = self.solve(n - 2, arr, memo) + arr[n]
		no = self.solve(n - 1, arr, memo)
		memo[n] = max(take, no)
		return memo[n]

	def FindMaxSum(self, a, n):
		if n == 1:
			return a[0]
		memo = [-1] * (n + 1)
		return self.solve(n - 1, a, memo)


class Solution:

	def findAns(self, a, i, j):
		if i > j:
			return 0
		return max(a[i] + self.findAns(a, i + 2, j), self.findAns(a, i + 1, j))

	def FindMaxSum(self, a, n):
		if n == 1:
			return a[0]
		prev = a[0]
		prev2 = 0
		for i in range(1, n):
			cur = max(a[i] + prev2, prev)
			prev2 = prev
			prev = cur
		return prev


class Solution:

	def FindMaxSum(self, a, n):
		if n == 1:
			return a[0]
		if n == 2:
			return max(a[0], a[1])
		first = a[0]
		second = max(a[0], a[1])
		i = 2
		while i < n:
			temp = second
			second = max(a[i] + first, second)
			first = temp
			i += 1
		return second


class Solution:

	def FindMaxSum(self, a, n):
		if n == 1:
			return a[0]
		prev2 = a[0]
		prev = max(a[0], a[1])
		for i in range(2, n):
			temp = max(a[i] + prev2, prev)
			prev2 = prev
			prev = temp
		return prev


class Solution:

	def FindMaxSum(self, arr, n):
		p1 = arr[0]
		p2 = 0
		for i in range(1, n):
			take = arr[i]
			if i > 1:
				take += p2
			noTake = p1 + 0
			p2 = p1
			p1 = max(take, noTake)
		return p1

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


class Solution:

	def FindMaxSum(self, arr, n):
		dp = [-1] * n
		return self.rec(n - 1, arr, dp)

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


import sys

class Solution:

	def __init__(self):
		self.dp = {}

	def findMaxSumUtil(self, a, n, m):
		if m >= n:
			return 0
		if m in self.dp:
			return self.dp[m]
		ans = max(a[m] + self.findMaxSumUtil(a, n, m + 2), self.findMaxSumUtil(a, n, m + 1))
		self.dp[m] = ans
		return ans

	def FindMaxSum(self, a, n):
		return self.findMaxSumUtil(a, n, 0)


class Solution:

	def FindMaxSum(self, a, n):
		prev = a[0]
		prev2 = 0
		for i in range(1, n):
			pick = a[i]
			if i > 1:
				pick += prev2
			non_pick = 0 + prev
			cur_i = max(pick, non_pick)
			prev2 = prev
			prev = cur_i
		return prev


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, a, n):
		dp = [-1] * n
		dp[0] = a[0]
		for i in range(1, n):
			if i - 2 < 0:
				temp = 0
			else:
				temp = dp[i - 2]
			pick = a[i] + temp
			non_pick = dp[i - 1]
			dp[i] = max(pick, non_pick)
		return dp[n - 1]


class Solution:

	def heist(self, idx, arr, dp):
		if idx == 0:
			return arr[0]
		if idx < 0:
			return 0
		if dp[idx] != -1:
			return dp[idx]
		pick = arr[idx] + self.heist(idx - 2, arr, dp)
		non_pick = self.heist(idx - 1, arr, dp)
		dp[idx] = max(pick, non_pick)
		return dp[idx]

	def FindMaxSum(self, a, n):
		dp = [-1] * n
		return self.heist(n - 1, a, dp)


class Solution:

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


class Solution:

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


class Solution:

	def FindMaxSum(self, a, n):
		import sys
		sys.setrecursionlimit(10 ** 9)
		dist = [-1] * n
		self.solve(n - 1, a, dist)
		return dist[n - 1]

	def solve(self, ind, arr, dp):
		if ind == 0:
			dp[ind] = arr[ind]
			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 = 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 FindMaxSum(self, arr, n):

		def f(arr):
			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
		ans = f(arr)
		return ans


class Solution:

	def FindMaxSum(self, a, n):
		second = 0
		first = a[0]
		for i in range(2, n + 1):
			(second, first) = (first, max(a[i - 1] + second, first))
		return first


class Solution:

	def FindMaxSum(self, nums, n):
		prev2 = 0
		prev = nums[0]
		for i in range(1, n):
			fh = nums[i]
			if i > 1:
				fh += prev2
			sh = 0 + prev
			prev2 = prev
			prev = max(fh, sh)
		return prev


from math import inf

class Solution:

	def FindMaxSum(self, a, n):
		if n == 1:
			return a[0]
		if n == 2:
			return max(a[0], a[1])
		tabarray = [-1] * n
		tabarray[0] = a[0]
		tabarray[1] = max(a[0], a[1])
		tabarray[-1] = -inf
		for i in range(2, n):
			tabarray[i] = max(tabarray[i - 1], tabarray[i - 2] + a[i])
		first = tabarray[n - 1]
		tabarray = [-1] * n
		tabarray[0] = -inf
		tabarray[1] = a[1]
		for i in range(2, n):
			tabarray[i] = max(tabarray[i - 1], tabarray[i - 2] + a[i])
		return max(first, tabarray[n - 1])


class Solution:

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


class Solution:

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


class Solution:

	def FindMaxSum(self, a, n):
		dp = [0 for i in range(n + 1)]
		data = a.copy()
		if n >= 1:
			dp[0] = data[0]
		if n >= 2:
			dp[1] = max(data[0], data[1])
		if n > 2:
			for i in range(2, n):
				cur = data[i]
				a = dp[i - 1]
				b = dp[i - 2] + cur
				dp[i] = max(a, b)
		return dp[n - 1]


class Solution:

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

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


class Solution:

	def FindMaxSum(self, a, n):
		self.a = a
		self.n = n
		dp = [0] * (n + 1)
		for i in range(n, -1, -1):
			if i >= n:
				dp[i] = 0
				continue
			way1 = a[i] + (0 if i + 2 > n else dp[i + 2])
			way2 = dp[i + 1]
			dp[i] = max(way1, way2)
		return dp[0]

	def steal(self, i):
		if i >= self.n:
			return 0
		way1 = self.a[i] + self.steal(i + 2)
		way2 = self.steal(i + 1)
		return max(way1, way2)


class Solution:

	def FindMaxSum(self, a, n):
		if n == 0:
			return 0
		high1 = a[0]
		if n == 1:
			return high1
		high2 = max(a[0], a[1])
		if n == 2:
			return high2
		for i in range(2, n):
			max_val = max(high1 + a[i], high2)
			high1 = high2
			high2 = max_val
		return max_val


class Solution:

	def FindMaxSum(self, a, n):
		takecurr = a[0]
		best = 0
		for i in range(1, n):
			(takecurr, best) = (best + a[i], max(best, takecurr))
		return max(best, takecurr)