Given an array A of size N. Find the maximum subset-sum of elements that you can make from the given array such that for every two consecutive elements in the array, at least one of the elements is present in our subset. 
Example 1:
Input: 
N = 4
A[] = {1, -1, 3, 4}
Output: 8
Explanation: 
We can choose 0th,2nd & 3rd index(0 based 
Index),so that it can satisfy the 
condition & can make maximum sum 8. 
Example 2:
Input: 
N = 3
A[] =  {0, 2, 0};
Output: 2
Explanation: 
We can choose 1st index. Here the 
maximum possible sum is 2.
Your task:
You don't have to read input or print anything. Your task is to complete the function findMaxSubsetSum() which takes the array A and its size N as input and returns the Maximum possible subset-sum.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
2 ≤ N ≤ 10^{5}
-10^{5 }≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: from typing import List



class Solution:

    def findMaxSubsetSum(self, N : int, A : List[int]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		(prev, curr) = ([0, A[0]], [0, 0])
		for i in range(1, N):
			(curr[0], curr[1], prev) = (prev[1], A[i] + max(prev), curr)
		return max(prev)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		(taken, notTaken) = (A[0], 0)
		for i in A[1:]:
			newTake = i + max(notTaken, taken)
			newNotTaken = taken
			(taken, notTaken) = (newTake, newNotTaken)
		return max(taken, notTaken)


from typing import *
import sys
sys.setrecursionlimit(10000000)

class Solution:

	def findMaxSubsetSum(self, N: int, arr: List[int]) -> int:
		dp = {}

		def f(i: int, maxNotPick: int) -> int:
			if i == N - 1:
				if maxNotPick > 0:
					return max(0, arr[i])
				return arr[i]
			if (i, maxNotPick) in dp:
				return dp[i, maxNotPick]
			pick = arr[i] + f(i + 1, 1)
			notPick = int(-1000000000.0)
			if maxNotPick:
				notPick = f(i + 1, maxNotPick - 1)
			dp[i, maxNotPick] = max(pick, notPick)
			return max(pick, notPick)

		def tab():
			dp = [[-1000000000.0] * 2 for i in range(N)]
			dp[0][0] = arr[0]
			dp[0][1] = max(arr[0], 0)
			for i in range(1, N):
				pick = arr[i] + dp[i - 1][1]
				notPick = dp[i - 1][0]
				dp[i][0] = max(pick, int(-1000000000.0))
				dp[i][1] = max(pick, notPick)
			return max(dp[N - 1][1], dp[N - 1][0])

		def space():
			notPick = arr[0]
			pick = max(arr[0], 0)
			for i in range(1, N):
				(notPick, pick) = (max(arr[i] + pick, int(-1000000000.0)), max(arr[i] + pick, notPick))
			return max(pick, notPick)
		return space()


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		dp = [0] * 3
		dp[0] = A[0]
		dp[1] = A[1] + max(A[0], 0)
		for i in range(2, N):
			dp[i % 3] = A[i] + max(dp[(i - 1) % 3], dp[(i - 2) % 3])
		return max(dp[(N - 2) % 3], dp[(N - 1) % 3])


from typing import List

class Solution:

	def findMaxSubsetSum(self, n: int, a: List[int]) -> int:
		s = 0
		i = 0
		l = [0]
		l1 = [a[0]]
		for i in range(1, n):
			l.append(l1[i - 1])
			l1.append(a[i] + max(l[i - 1], l1[i - 1]))
		return max(l[n - 1], l1[n - 1])


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		prev0 = A[0]
		prev1 = 0
		c0 = 0
		c1 = 1
		for i in range(1, N):
			l = prev0
			prev0 = max(prev0 + A[i], prev1 + A[i])
			prev1 = l
		return max(prev1, prev0)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		take = n_take = 0
		for i in A:
			(take, n_take) = (max(i + take, n_take), i + take)
		return max(take, n_take)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		(takeFirst, takeSecond) = (A[0], 0)
		for i in range(1, N):
			takeSecond = max(takeFirst, takeSecond) + A[i]
			(takeSecond, takeFirst) = (takeFirst, takeSecond)
		return max(takeFirst, takeSecond)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		curr = 0
		curr_n = 0
		i = 0
		while i < N:
			(curr, curr_n) = (max(curr_n, curr + A[i]), curr + A[i])
			i += 1
		return max(curr, curr_n)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		suma = 0
		max_n = A[0]
		for i in range(1, N):
			current = A[i] + max(suma, max_n)
			suma = max_n
			max_n = current
		return max(suma, max_n)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		(a, b) = (A[0], 0)
		for i in A[1:]:
			newa = i + max(a, b)
			newb = a
			(a, b) = (newa, newb)
		return max(a, b)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		a = 0
		b = 0
		for value in A:
			(a, b) = (max(b + value, a + value), a)
		return max(a, b)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		(t, nt) = (A[0], 0)
		for i in A[1:]:
			nt = i + max(nt, t)
			nnt = t
			(t, nt) = (nt, nnt)
		return max(t, nt)


from typing import List

class Solution:

	def findMaxSubsetSum(self, n: int, arr: List[int]) -> int:
		rightTake = 0
		rightNotTake = 0
		for i in range(n - 1, -1, -1):
			a = max(rightNotTake + arr[i], rightTake + arr[i])
			b = rightTake
			(rightTake, rightNotTake) = (a, b)
		return max(rightTake, rightNotTake)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		(first, second) = (A[0], 0)
		for i in range(1, N):
			second = max(first, second) + A[i]
			(first, second) = (second, first)
		return max(first, second)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, a: List[int]) -> int:
		tk = n_tk = 0
		for i in a:
			(tk, n_tk) = (max(i + tk, n_tk), i + tk)
		return max(tk, n_tk)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		temp = res = 0
		for i in A:
			(temp, res) = (max(i + temp, res), i + temp)
		return max(temp, res)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		t = k = 0
		for i in A:
			(t, k) = (max(i + t, k), i + t)
		return max(t, k)


from typing import List

class Solution:

	def findMaxSubsetSum(self, n: int, a: List[int]) -> int:
		take = n_take = 0
		for i in a:
			(take, n_take) = (max(i + take, n_take), i + take)
		return max(take, n_take)


from typing import List

class Solution:

	def findMaxSubsetSum(self, n: int, A: List[int]) -> int:
		(a, b) = (0, 0)
		for i in A:
			(a, b) = (max(i + a, b), i + a)
		return max(a, b)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		i = j = 0
		for p in A:
			(i, j) = (max(p + i, j), p + i)
		return max(i, j)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		take = A[0]
		ntake = 0
		for i in range(1, N):
			newtake = max(ntake + A[i], take + A[i])
			newntake = take
			take = newtake
			ntake = newntake
		return max(take, ntake)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		sm = 0
		mx = A[0]
		for i in range(1, N):
			cur = A[i] + max(sm, mx)
			sm = mx
			mx = cur
		return max(sm, mx)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, arr: List[int]) -> int:
		prev_taken = arr[0]
		prev_not_taken = 0
		for i in range(1, N):
			curr_taken = arr[i] + max(prev_taken, prev_not_taken)
			curr_not_taken = prev_taken
			prev_taken = curr_taken
			prev_not_taken = curr_not_taken
		return max(prev_taken, prev_not_taken)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		t1 = t2 = 0
		for i in A:
			(t1, t2) = (max(i + t1, t2), i + t1)
		return max(t1, t2)


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		dp = [[None] * 2 for _ in range(N)]
		dp[0] = [A[0], 0]
		for idx in range(1, N):
			dp[idx][1] = dp[idx - 1][0]
			dp[idx][0] = max(dp[idx - 1]) + A[idx]
		return max(dp[N - 1])


from typing import List

class Solution:

	def findMaxSubsetSum(self, N: int, A: List[int]) -> int:
		(not_taken, taken) = (0, 0)
		for e in A:
			(taken, not_taken) = (max(not_taken, taken) + e, taken)
		return max(taken, not_taken)