Problem:
 Score : 600 points    Problem Statement Given is an integer sequence A_1, ..., A_N of length N .  We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.  Find the maximum possible sum of the chosen elements.  Here \lfloor x \rfloor denotes the greatest integer not greater than x .      Constraints  2 \leq N \leq 2\times 10^5  |A_i|\leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  ...  A_N       Output Print the maximum possible sum of the chosen elements.        Sample Input 1 6
1 2 3 4 5 6      Sample Output 1 12  Choosing 2 , 4 , and 6 makes the sum 12 , which is the maximum possible value.       Sample Input 2 5
-1000 -100 -10 0 10      Sample Output 2 0  Choosing -10 and 10 makes the sum 0 , which is the maximum possible value.       Sample Input 3 10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000      Sample Output 3 5000000000  Watch out for overflow.       Sample Input 4 27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49      Sample Output 4 295

Solution (Python):
import collections, sys
sys.setrecursionlimit(100005)
N = int(input())
A = [int(_) for _ in input().split()]
INF = float('inf')
memo = collections.defaultdict(lambda: INF)


def c(start, res):
    if memo[start, res] != INF:
        return memo[start, res]
    elif 2 * res - 1 > N - start:
        memo[start, res] = -INF
    elif start >= N:
        memo[start, res] = -INF
    elif res > 1:
        memo[start, res] = max(A[start] + c(start + 2, res - 1),
                               c(start + 1, res), c(start + 2, res))
    else:
        memo[start, res] = max(A[start], c(start + 1, res))
    return memo[start, res]


print(c(0, N // 2))

Solution (Python):
import collections, sys
sys.setrecursionlimit(100005)
N = int(input())
A = [int(_) for _ in input().split()]
INF = float('inf')
memo = collections.defaultdict(lambda: INF)


def c(start, res):
    if memo[start, res] != INF:
        return memo[start, res]
    elif 2 * res - 1 > N - start:
        memo[start, res] = -INF
    elif start >= N:
        memo[start, res] = -INF
    elif res > 1:
        memo[start, res] = max(A[start] + c(start + 2, res - 1),
                               c(start + 1, res), c(start + 2, res))
    else:
        memo[start, res] = max(A[start], c(start + 1, res))
    return memo[start, res]


print(c(0, N // 2))

Solution (Python):


N = int(input())
A = [int(hoge) for hoge in input().split()]
DP = [[0]*3 for n in range(N)] 

DP[0][0] = A[0]

for n in range(1,N):
    
    DP[n][0] = DP[n-2][0] + A[n]
    DP[n][1] = max((DP[n-2][1]+A[n],DP[n-1][0]))
    DP[n][2] = max((DP[n-2][2]+A[n],DP[n-1][1]))
if N%2:
    print(DP[n][2])
else:
    print(DP[n][1])

Solution (Python):
from collections import defaultdict
INF = 10 ** 15
N = int(input())
A = list(map(int,input().split()))
dp_take = defaultdict(lambda: -INF)
dp_not = defaultdict(lambda: -INF)
dp_take[(0,0)] = 0
dp_not[(0,0)] = 0

for i in range(N):
    for j in range((i + 1) // 2 - 1, (i + 2) // 2 + 1):
        if j > 0:
            dp_take[(i+1, j)] = max(dp_take[(i+1, j)], dp_not[(i, j-1)] + A[i])
        dp_not[(i+1, j)] = max(dp_not[(i, j)], dp_take[(i, j)])

print(max(dp_take[(N, N//2)], dp_not[(N, N//2)]))

Solution (Python):
def find(A):
    N = len(A)
    ans = [0]*N
    odd_sum = [0]*N
    even_sum = [0]*N
    for i in range(N):
        if i%2 == 0:
            if i-2>=0:
                even_sum[i] = even_sum[i-2] + A[i]
            else:
                even_sum[i] = A[i]
        else:
            if i-2>=0:
                odd_sum[i] = odd_sum[i-2] + A[i]
            else:
                odd_sum[i] = A[i]



    for i in range(1,N):
        length = i+1
        if length%2==0:
            ans[i] = max(A[i] + ans[i-2],odd_sum[i-1]+even_sum[i-1] )
        else:
            ans[i] = max(A[i] + ans[i-2],ans[i-1])
            
    return ans[-1]
    
input()   
print(find(list(map(int,input().strip().split()))))

Solution (Python):
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random



def inp():
    re = map(int, raw_input().split())
    if len(re) == 1:
        return re[0]
    return re

def inst():
    return raw_input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def get(n, da):
    mx = 0
    for i in range(n):
        if i%2==1:
            mx += da[i]
    st = [0 for i in range(n)]
    dp = [0 for i in range(n)]
    st[0]=1
    dp[0]=da[0]
    for i in range(2,n):
        if i%2==0:
            st[i]=1
            dp[i]=dp[i-2]+da[i]
        else:
            st[i]=1
            dp[i] = dp[i-3]+da[i]
            if st[i-2]:
                dp[i] = max(dp[i], dp[i-2]+da[i])
    return max(mx, max(dp[n-1], dp[n-2]))

def my_main():
    n = inp()
    da = inp()
    if n%2==0:
        print get(n, da)
    else:
        nda = [da[i] for i in range(n) if i%2==0]
        mx = sum(nda) - min(nda)
        mx = max(mx, max(get(n-1, da[1:]), get(n-1, da[:-1])))
        st = [[0 for i in range(n)]for i in range(3)]
        dp = [[0 for i in range(n)]for i in range(3)]
        st[0][0]=1
        dp[0][0]=da[0]
        for i in range(2,n):
            if st[0][i-2]:
                st[0][i] = 1
                dp[0][i] = dp[0][i-2] + da[i]
            if i-3 >= 0 and st[0][i-3]:
                st[1][i] = 1
                dp[1][i] = dp[0][i-3] + da[i]
            if st[1][i-2]:
                st[1][i] = 1
                dp[1][i] = max(dp[1][i], dp[1][i-2] + da[i])
            if i-3>=0 and st[1][i-3]:
                st[2][i] = 1
                dp[2][i] = dp[1][i-3] + da[i]
            if st[2][i-2]:
                if st[2][i]:
                    dp[2][i] = max(dp[2][i], dp[2][i-2]+da[i])
                else:
                    st[2][i] = 1
                    dp[2][i] = dp[2][i-2]+da[i]
        print max(mx, dp[2][n-1])







my_main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
dp = [[0] * 4 for _ in range(200005)]
k = 1 + N % 2
for i in range(N + 1):
    for j in range(k + 1):
        dp[i][j] = - float('inf')
dp[0][0] = 0
for i in range(N):
    for j in range(k + 1):
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
        now = dp[i][j]
        if (i + j) % 2 == 0:
            now += A[i]
        dp[i + 1][j] = max(dp[i + 1][j], now)
ans = dp[N][k]
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()
dp = [[defaultdict(lambda:-INF) for _ in range(2)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
    for j in range(2):
        for k, e in dp[i][j].items():
            if i // 2 <= k <= i // 2 + 1:
                dp[i + 1][0][k] = max(dp[i + 1][0][k], e)
            if i // 2 <= k + 1 <= i // 2 + 1 and j == 0:
                dp[i + 1][1][k + 1] = max(dp[i + 1][1][k + 1], e + A[i])

print(max(dp[n][0][n // 2], dp[n][1][n // 2]))

Solution (Python):
from collections import defaultdict
n=int(input())
a=[int(i) for i in input().split()]
INF=float('inf')
dp0=defaultdict(lambda: -INF)
dp1=defaultdict(lambda: -INF)
dp0[(0,0)]=0
for i in range(1,n+1):
  for j in range(i//2-1,(i+1)//2+1):
    dp0[(i,j)]=max(dp0[(i-1,j)],dp1[(i-1,j)])
    dp1[(i,j)]=dp0[(i-1,j-1)]+a[i-1]
print(max(dp0[(n,n//2)],dp1[(n,n//2)]))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
INF = 1001001001001001
c = n//2
dp = [[-INF]*3 for _ in range(c+1)]
dp[0][0] = 0
for i in range(c+1):
    for j in range(3):
        for k in range(3):
            if i+1<=c and j+k<3 and 2*i+j+k<n:
                dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j]+a[2*i+j+k])

ans = -INF

for i in range(3):
    ans = max(ans,dp[c][i])

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
inf = -float('inf')
a = list(map(int, readline().split())) + [inf] * 2
dp = [[inf] * 3 for _ in range(n + 4)]
for i in range(3):
    dp[0][i] = 0
for i, (bf, aa, af) in enumerate(zip(a, a[1:], a[2:])):
    dp[i + 4][2] = max(dp[i + 4][2], dp[i][0] + af)
    for j in range(1, 3):
        dp[i + 3][j] = max(dp[i + 3][j], dp[i][j - 1] + aa)
    for j in range(3):
        if dp[i + 2][j] != inf or j == 0:
            dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + bf)
if n % 2 == 0:
    print(max(dp[n + 1][1], dp[n][0]))
else:
    print(max(dp[n + 1][2], dp[n][1], dp[n - 1][0]))

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))

dp = [0]*n
c = a[0]
dp[1] = max(a[0],a[1])

for i in range(2,n):
    if i%2 == 0:
        c += a[i]
        dp[i] = max(dp[i-2]+a[i],dp[i-1])
    else:
        dp[i] = max(dp[i-2]+a[i],c)

print(dp[-1])

Solution (Python):
import sys

N = int(input())
A = list(map(int,input().split()))

INF = 10**20
dp = [[[-INF]*2 for _ in range(2)] for _ in range(N+1)]


if N&1:
    dp[0][1][0] = 0
    for i in range(N):
        if i&1:
            dp[i+1][0][0] = max(dp[i][0][0], dp[i][0][1])
            dp[i+1][1][0] = max(dp[i][1][0], dp[i][1][1])
            dp[i+1][1][1] = dp[i][0][0] + A[i]

        else:
            dp[i+1][0][0] = max(dp[i][1][0], dp[i][1][1])
            dp[i+1][0][1] = dp[i][0][0] + A[i]
            dp[i+1][1][1] = dp[i][1][0] + A[i]

    ans = max(dp[N][0][0], dp[N][0][1])            

else:
    dp[0][1][0] = 0
    for i in range(N):
        if i&1:
            dp[i+1][1][0] = dp[i][1][1]
            dp[i+1][1][1] = dp[i][0][0] + A[i]            

        else:
            dp[i+1][0][0] = max(dp[i][1][0], dp[i][1][1])
            dp[i+1][1][1] = dp[i][1][0] + A[i]
    ans = max(dp[N][1][0], dp[N][1][1])

print(ans)

Solution (Python):
INF = 10**18

def solve(n, a):
    
    dp = [{j: [-INF, -INF] for j in range(i//2-1, (i+1)//2 + 1)} for i in range(n+1)]
    dp[0][0][False] = 0
    for i in range(n):
        for j in dp[i].keys():
            if (j+1) in dp[i+1]:
                dp[i+1][j+1][True] = max(dp[i+1][j+1][True], dp[i][j][False] + a[i])
            if j in dp[i+1]:
                dp[i+1][j][False] = max(dp[i+1][j][False], dp[i][j][False])
                dp[i+1][j][False] = max(dp[i+1][j][False], dp[i][j][True])
    return max(dp[n][n//2])

n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[[-float("inf")]*2 for j in range(3)] for i in range(n+1)]
    
    dp[0][0][0] = 0
    for i in range(n):
        x = a[i]
        if i%2 == 0:
            for j in range(-1, 2):
                dp[i+1][j][0] = max(dp[i][j][0], dp[i][j][1])
            for j in range(-1, 1):
                dp[i+1][j+1][1] = dp[i][j][0] + x
        else:
            for j in range(-1, 1):
                dp[i+1][j][0] = max(dp[i][j+1][0], dp[i][j+1][1])
            for j in range(-1, 2):
                dp[i+1][j][1] = dp[i][j][0] + x
    print(max(dp[n][0][0], dp[n][0][1]))

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

if n==2:
    print(max(a))
    exit()

dp = [0]*n
ep = [0]*n

dp[1] = max(a[:2])
dp[2] = max(a[:3])

ep[1] = a[0]
ep[2] = max(a[:2])

for i in range(3,n):
    if (i+1)%2==0:
        ep[i] = ep[i-2] + a[i-1]
    else:
        ep[i] = max(ep[i-2]+a[i-1],ep[i-3]+a[i-2])
    dp[i] = max(dp[i-2]+a[i],ep[i])

print(dp[-1])

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
dp=[0]
sum_odd=a[0]

dp.append(0)
for i in range(2,n+1):
  if i%2==1:
    sum_odd+=a[i-1]
    dp.append(max(dp[i-1],dp[i-2]+a[i-1]))
  else:
    dp.append(max(sum_odd,a[i-1]+dp[i-2]))
print(dp[n])

Solution (Python):
import sys
input=lambda :sys.stdin.readline().rstrip()

n = int(input())
A = list(map(int, input().split()))

k = 1+n%2
f_inf = float('inf')

dp = [[-f_inf for _ in range(4)] for _ in range(200005)]
dp[0][0] = 0
for i in range(n):
    for j in range(k+1):
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
        now = dp[i][j]
        if (i+j)%2 == 0: now += A[i]
        dp[i+1][j] = max(dp[i+1][j], now)

ans = dp[n][k]
print(ans)

Solution (Python):
N, *A = map(int, open(0).read().split())

dp = [[-10 ** 10] * 3 for _ in range(N + 1)]
dp[0] = [0] * 3
dp[1][0] = A[0]
dp[2][1] = A[1]
for i in range(2, N):
    dp[i + 1][0] = dp[i - 1][0] + A[i]
    dp[i + 1][1] = max(dp[i - 1][1], dp[i - 2][0]) + A[i]
    dp[i + 1][2] = max(dp[i - 1][2], dp[i - 2][1], dp[i - 3][0]) + A[i]

if N % 2 == 1:
    print(max(dp[-3][0], dp[-2][1], dp[-1][2]))
else:
    print(max(dp[-2][0], dp[-1][1]))

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
m=n//2
if n%2==0:
    dp=[[-10**18]*2 for _ in range(m)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)):
            for k in range(2*(i-1),2*i):
                if j-k>1:
                    dp[i][j%2]=max(dp[i][j%2],dp[i-1][k%2]+a[j])
else:
    dp=[[-10**18]*3 for _ in range(m)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    dp[0][2]=a[2]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)+1):
            for k in range(2*(i-1),2*i+1):
                if j-k>1:
                    dp[i][j-2*i]=max(dp[i][j-2*i],dp[i-1][k-2*(i-1)]+a[j])
print(max(dp[-1]))

Solution (Python):
from collections import defaultdict
N,*A = map(int, open(0).read().split())
dp_not = defaultdict(lambda :-10**18)
dp_take = defaultdict(lambda :-10**18)
dp_not[(0,0)] = 0
for i,x in enumerate(A,1):
  for j in range(N//2-(N-i+1)//2,(i+1)//2+1):
    dp_not[(i,j)] = max(dp_not[(i-1,j)],dp_take[(i-1,j)])
    dp_take[(i,j)] = dp_not[(i-1,j-1)] + x
print(max(dp_not[(N,N//2)], dp_take[(N,N//2)]))

Solution (Python):
from collections import defaultdict
N,*A = map(int, open(0).read().split())
dp_not = defaultdict(lambda :-10**18)
dp_take = defaultdict(lambda :-10**18)
dp_not[(0,0)] = 0
for i,x in enumerate(A,1):
  for j in ((i-1)//2,(i-1)//2+1):
    dp_not[(i,j)] = max(dp_not[(i-1,j)],dp_take[(i-1,j)])
    dp_take[(i,j)] = dp_not[(i-1,j-1)] + x
print(max(dp_not[(N,N//2)], dp_take[(N,N//2)]))

Solution (Python):
from collections import defaultdict

n=int(input())
a=list(map(int,input().split()))




dp=defaultdict(lambda:-pow(10,18))
dp[(1,1)]=a[0]
for i in range(2,n+1): 
      for j in range(i//2-1,(i+1)//2+1):
            if j==1:
                  dp[(i,j)]=max(dp[(i-1,1)],a[i-1])
            elif j==0:
                  dp[(i,j)]=0
            else:
                  dp[(i,j)]=max(dp[(i-2,j-1)]+a[i-1],dp[(i-1,j)])
print(dp[(n,n//2)])

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
dp = [[[0,0,0] for i in range(2)] for i in range(n+1)]
for i in range(1,n+1):
    if i%2 == 1:
        if i > 1:
            dp[i][0][1] = dp[i-1][1][0]+A[i-1]
            dp[i][0][2] = dp[i-1][1][1]+A[i-1]
            dp[i][1][0] = max(dp[i-1][0][0],dp[i-1][1][0])
            dp[i][1][1] = max(dp[i-1][0][1],dp[i-1][1][1])
        else:
            dp[i][0][2] = A[0]
    else:
        dp[i][0][0] = dp[i-1][1][0]+A[i-1]
        dp[i][0][1] = dp[i-1][1][1]+A[i-1]
        dp[i][1][0] = max(dp[i-1][0][1],dp[i-1][1][1])
        dp[i][1][1] = dp[i-1][0][2]
if n%2 == 0:
    print(max(dp[n][0][1],dp[n][1][1]))
else:
    print(max(dp[n][0][1],dp[n][1][1]))

Solution (Python):
from collections import defaultdict

N = int(input())
A = list(map(int,input().split()))

DP = defaultdict(lambda: -10**18)

DP[(0,0)] = A[0]

for i in range(1,N):
    for j in range((i+1)//2-1,(i+2)//2):
        if j == 0:
            DP[(i,0)] = max(DP[(i-1,0)],A[i])
        else:
            DP[(i,j)] = max(DP[(i-1,j)],DP[(i-2,j-1)]+A[i])

print(DP[(N-1,N//2-1)])

Solution (Python):
N = int(input())
K = N % 2 + 1
A = tuple(map(int, input().split()))
table = [[-float("inf")] * (K + 2) for _ in range(N + 1)]
table[0][0] = 0
for i in range(N):
    for j in range(K + 1):
        table[i + 1][j] = max(table[i][j] + (A[i] if not (i + j) % 2 else 0), table[i + 1][j])
        table[i + 1][j + 1] = max(table[i][j], table[i + 1][j + 1])
print(table[N][K])

Solution (Python):

import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict

def main():
	
	n = int(input())
	l = [int(j) for j in input().split()]
	dp = dict()
	dp[0,0] = 0
	dp[2,1] = max(l[0], l[1])
	dp[1,1] = l[0]
	dp[2,2] = -1e14
	dp[1, 0] = 0
	for i in range(3,n+1):
		for j in [(i//2), (i+1)//2]:
			
			
			dp[i, j] = dp[i-2, j-1]+l[i-1]
			if i>=2*j:
				dp[i, j] = max(dp[i-2, j-1]+l[i-1], dp[i-1, j])				
				
			
			

			
	print(dp[n, (n)//2])
		




BUFSIZE = 8192


class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = "x" in file.mode or "r" not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b"\n") + (not b)
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode("ascii"))
		self.read = lambda: self.buffer.read().decode("ascii")
		self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = list(map(int,input().split()))
    INF = -10**15
    
    dp = [[[INF,INF],[False,False]] for _ in range(N)]
    dp[0][0][0],dp[0][0][1],dp[0][1][1] = 0,a[0],True
    dp[1][0][0] = 0
    if a[0] < a[1]:
        dp[1][0][1],dp[1][1][1] = a[1],True
    else:
        dp[1][0][1] = a[0]
    
    for i in range(2,N):
        if i%2 != 0:
            dp[i][0][0] = dp[i-1][0][0]
            if dp[i][0][0] < dp[i-2][0][0]+a[i]:
                dp[i][0][0] = dp[i-2][0][0]+a[i]
                dp[i][1][0] = True
            dp[i][0][1] = dp[i-1][0][1]
            if dp[i-1][1][0] == False:
                if dp[i][0][1] < dp[i-1][0][0]+a[i]:
                    dp[i][0][1] = dp[i-1][0][0]+a[i]
                    dp[i][1][1] = True
            if dp[i][0][1] < dp[i-2][0][1]+a[i]:
                dp[i][0][1] = dp[i-2][0][1]+a[i]
                dp[i][1][1] = True
        else:
            dp[i][0][0] = dp[i-1][0][1]
            if dp[i-1][1][0] == False:
                if dp[i][0][0] < dp[i-1][0][0]+a[i]:
                    dp[i][0][0] = dp[i-1][0][0]+a[i]
                    dp[i][1][0] = True
            if dp[i][0][0] < dp[i-2][0][0]+a[i]:
                dp[i][0][0] = dp[i-2][0][0]+a[i]
                dp[i][1][0] = True
            dp[i][0][1] = dp[i-2][0][1]+a[i]
            if dp[i-1][1][1] == False:
                if dp[i][0][1] < dp[i-1][0][1]+a[i]:
                    dp[i][0][1] = dp[i-1][0][1]+a[i]
            dp[i][1][1] = True
    
    if N%2 == 0:
        print(dp[-1][0][1])
    else:
        print(dp[-1][0][0])
 
if __name__ == "__main__":
    main()

Solution (Python):
import math
n=int(input())
a=list(map(int, input().split()))
dp=[0]*n
dp[0]=0
dp[1]=max(a[0],a[1])
curr=a[0]
for i in range(2,n):
  if i&1==1:
    curr+=a[i-1]
    dp[i]=max(curr,dp[i-2]+a[i])
  else: dp[i]=max(dp[i-2]+a[i],dp[i-1])
print(dp[n-1])

Solution (Python):
n=int(input())
a = list(map(int,input().split()))
x0,x1,x2,o0,o1,o2=a[0],-10**18,0,-10**18,a[1],-10**18
for i in a[2:]:
  x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
print(max(x0,x1,o1)if n%2==0 else max(x1,x2,o2))

Solution (Python):
n=int(input())
a = list(map(int,input().split()))






x0,x1,x2,o0,o1,o2=a[0],-10**18,0,-10**18,a[1],-10**18
for i in a[2:]:
    x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
if n%2==0:
    print(max(x0,x1,o1))
else:
    print(max(x1,x2,o2))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
iseven=(n%2==0)

if n==2:
    print(max(a))
    exit()
dp = [[-float("inf") for _ in range(3)] for _ in range(n)]
dp[0][0]=a[0]
dp[1][1]=a[1]
if n>2:
    dp[2][2]=a[2]

for i in range(n):
    for k in range(3):
        if i+2<n:
            dp[i+2][k] = max(dp[i+2][k], dp[i][k] + a[i+2])
        if k<=1 and i+3<n:
            dp[i+3][k+1] = max(dp[i+3][k+1], dp[i][k] + a[i+3])
        if not iseven and k==0 and i+4<n:
            dp[i+4][k+2] = max(dp[i+4][k+2], dp[i][k] + a[i+4])


if iseven:
    ans=max([dp[-1][0],dp[-1][1]])
else:
    ans=max([dp[-3][0],dp[-2][1],dp[-1][2]])
print(ans)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
if n%2==0:
    ans1=A[0];ans2=A[1]
    for i in range((n-2)//2):
        ans2 = max(ans1,ans2)+A[(i+1)*2+1]
        ans1 = ans1++A[(i+1)*2]
    print(max([ans1,ans2]))

else:
    ans1,ans2,ans3,=A[0],A[1],A[2]
    for i in range((n-2)//2):
        ans3 = max(ans3,ans2) + A[(i+2)*2]
        ans2 = max(ans1,ans2) + A[(i+2)*2-1]
        ans1 = ans1 + A[(i+1)*2]
    print(max([ans1,ans2,ans3]))

Solution (Python):
n=int(input())
if n%2:
  a=list(map(int,input().split()))
  s=[[a[0],0,0],[0,a[1],0],[a[0]+a[2],0,a[2]]]+[[0,0,0]for i in range(3,n)]
  for i in range(3,n):
    if i%2:
      s[i][1]=max(s[i-2][1],s[i-3][0])+a[i]
    else:
      s[i][0]=s[i-2][0]+a[i]
      s[i][2]=max([s[i-2][2],s[i-3][1],s[i-4][0]])+a[i]
  print(max([s[-1][2],s[-2][1],s[-3][0]]))
else:
  a=list(map(int,input().split()))
  s=[a[0],a[1]]+[0 for i in range(2,n)]
  for i in range(2,n):
    if i%2:
      s[i]=max([s[i-2],s[i-3]])+a[i]
    else:
      s[i]=s[i-2]+a[i]
  print(max(s[-2:]))

Solution (Python):
from collections import defaultdict

def main():
    INF = float("inf")

    N, *A = map(int, open(0).read().split())

    dp_in = defaultdict(lambda: -INF)

    dp_out = defaultdict(lambda: -INF)
    dp_out[(0, 0)] = 0

    for i, a in enumerate(A, 1):
        p = i // 2
        for j in [p - 1, p, p + 1]:
            dp_in[(i, j)] = a + dp_out[(i - 1, j - 1)]
            dp_out[(i, j)] = max(dp_in[(i - 1, j)], dp_out[(i - 1, j)])

    print(max(dp_in[(N, N // 2)], dp_out[(N, N // 2)]))

main()

Solution (Python):
from collections import defaultdict

INF = float("inf")

N, *A = map(int, open(0).read().split())

dp_in = defaultdict(lambda: -INF)

dp_out = defaultdict(lambda: -INF)
dp_out[(0, 0)] = 0

for i, a in enumerate(A, 1):
    p = i // 2
    for j in [p - 1, p, p + 1]:
        dp_in[(i, j)] = a + dp_out[(i - 1, j - 1)]
        dp_out[(i, j)] = max(dp_in[(i - 1, j)], dp_out[(i - 1, j)])

print(max(dp_in[(N, N // 2)], dp_out[(N, N // 2)]))

Solution (Python):
from collections import defaultdict

INF = float("inf")

N, *A = map(int, open(0).read().split())

dp = defaultdict(lambda: -INF)
dp[(0, 0, False)] = 0

for i, a in enumerate(A, 1):
    p = i // 2
    for j in [p - 1, p, p + 1]:
        dp[(i, j, True)] = a + dp[(i - 1, j - 1, False)]
        dp[(i, j, False)] = max(dp[(i - 1, j, False)], dp[(i - 1, j, True)])

print(max(dp[(N, N // 2, True)], dp[(N, N // 2, False)]))

Solution (Python):
from collections import defaultdict

INF = float("inf")

N, *A = map(int, open(0).read().split())

dp = defaultdict(lambda: -INF)
dp[(0, 0, False)] = 0

for i, a in enumerate(A, 1):
    p = i // 2
    for j in [p - 1, p, p + 1]:
        dp[(i, j, True)] = a + dp[(i - 1, j - 1, False)]
        dp[(i, j, False)] = max(dp[(i - 1, j, False)], dp[(i - 1, j, True)])

print(max(dp[(N, N // 2, True)], dp[(N, N // 2, False)]))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n = II()
    a = LI()
    if n == 3:
        print(max(a))
        return
    dp = [[-inf] * 3 for i in range(n + 1)]
    dp[0] = [0, 0, 0]
    dp[1][0] = a[0]
    dp[2][1] = a[1]
    for i in range(3, n+1):
        dp[i][0] = dp[i - 2][0] + a[i-1]
        dp[i][1] = max(dp[i - 2][1], dp[i - 3][0]) + a[i-1]
        dp[i][2] = max(dp[i - 2][2], dp[i - 3][1], dp[i - 4][0]) + a[i-1]
    if n & 1:
        print(max(dp[-3][0], dp[-2][1], dp[-1][2]))
    else:
        print(max(dp[-1][1], dp[-2][0]))
    return



if __name__ == '__main__':
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n = II()
    a = LI()
    if n == 3:
        print(max(a))
        return
    dp = [[-inf] * 3 for i in range(n + 1)]
    dp[0] = [0, 0, 0]
    dp[1][0] = a[0]
    dp[2][1] = a[1]
    for i in range(3, n+1):
        dp[i][0] = dp[i - 2][0] + a[i-1]
        dp[i][1] = max(dp[i - 2][1], dp[i - 3][0]) + a[i-1]
        dp[i][2] = max(dp[i - 2][2], dp[i - 3][1], dp[i - 4][0]) + a[i-1]
    if n & 1:
        print(max(dp[-3][0], dp[-1][1], dp[-1][2]))
    else:
        print(max(dp[-1][1], dp[-2][0]))
    return



if __name__ == '__main__':
    solve()

Solution (Python):

import sys

MOD = 1000000007

def solve(N: int, A: "List[int]"):
    from collections import defaultdict
    M = N // 2
    def get_range(idx):
        r = (N - idx) // 2 + 1        
        return range(max(0, M-r), idx//2+1+1)
    
    dp_a = defaultdict(lambda:-float('inf'))
    dp_s = defaultdict(lambda:-float('inf'))
    dp_s[(0, -1)] = 0 
    for i in range(N):
        for j in get_range(i):
            dp_s[(j, i)] = max(dp_s[(j, i)], dp_a[(j, i-1)], dp_s[(j, i-1)])
            dp_a[(j, i)] = max(dp_a[(j, i)], dp_s[(j, i)], dp_s[(j-1, i-1)]+A[i])
    print(max(max(v for (j, i), v in dp_a.items() if j == M),
              max(v for (j, i), v in dp_s.items() if j == M)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
m = n//2
INF = 10**18
dp = [defaultdict(lambda: -INF) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(i//2-1, (i+1)//2+1):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i-1])
        elif 0 <= i-2 and 0 <= j <= m:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
print(dp[-1][m])

Solution (Python):
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
m = n//2
INF = 10**18
dp = [defaultdict(lambda: -INF) for _ in range(n+1)]
for i in range(1, n+1):
    L = i//2-1
    R = (i+1)//2+1
    for j in range(L, R):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i-1])
        elif 0 <= i-2 and 0 <= j <= m:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
print(dp[-1][m])

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int,input().split()))
dp0 = [0] * (n+11)
dp1 = [0] * (n+11)
dp2 = [0] * (n+11)
for i,ai in enumerate(A):
  dp2[i+11] = (max(dp0[i+7] + ai, dp1[i+8] + ai, dp2[i+9] + ai) if i >= 2 else 0)
  dp1[i+11] = (max(dp0[i+8] + ai, dp1[i+9] + ai) if i >= 1 else 0)
  dp0[i+11] = dp0[i+9] + ai 
if n % 2 == 0:
  print(max(dp0[n + 9], dp1[n + 10]))
else:
  print(max(dp0[n + 8], dp1[n + 9], dp2[n + 10]))

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int,input().split()))
dp0 = [0] * (n+11)
dp1 = [0] * (n+11)
dp2 = [0] * (n+11)
for i,ai in enumerate(A):
  dp2[i+11] = (max(dp0[i+7] + ai, dp1[i+8] + ai, dp2[i+9] + ai) if i >= 2 else 0)
  dp1[i+11] = (max(dp0[i+8] + ai, dp1[i+9] + ai) if i >= 1 else 0)
  dp0[i+11] = dp0[i+9] + ai 
if n % 2 == 0:
  print(max(dp0[n + 9], dp1[n + 10]))
else:
  print(max(dp0[n + 8], dp1[n + 9], dp2[n + 10]))