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):
n,*l=map(int,open(0).read().split());p=[0]*n;d=p[:]
for i,l in enumerate(l):p[i]+=l+p[i-2];d[i]=max(l+d[i-2],[d,p][i&1][i-1])
print(d[-1])

Solution (Python):
n=int(input())
a=[int(j) for j in input().split()]
p=[0]*n
d=[0]*n
for i in range(n):
    p[i]=a[i]+p[i-2]
    if (i&1):
        d[i]=max(p[i-1],a[i]+d[i-2])
    else:
        d[i]=max(d[i-1],a[i]+d[i-2])
print(d[-1])

Solution (Python):
N = int(input())
A = [0, 0]+list(map(int, input().split()))+[0, 0]
skip = N-2*(N//2)+1
dp = [[-10**18]*(skip+1) for _ in range(N+4)]

for i in range(2):
    for j in range(skip+1):
        dp[i][j] = 0

for i in range(2, N+4):
    for j in range(skip+1):
        dp[i][j] = max(dp[i][j], dp[i-2][j]+A[i])
        
        if i>=3 and j+1<=skip:
            dp[i][j+1] = max(dp[i][j+1], dp[i-3][j]+A[i])
        
        if i>=4 and j+2<=skip:
            dp[i][j+2] = max(dp[i][j+2], dp[i-4][j]+A[i])

print(dp[N+3][skip])

Solution (Python):
n=int(input());l=list(map(int,input().split()));p=[0]*n;d=[0]*n
for i in range(n):p[i]=l[i]+p[i-2];d[i]=max(p[i-1]if i&1else d[i-1],l[i]+d[i-2])
print(d[-1])

Solution (Python):
n=int(input());l=list(map(int,input().split()));p=[0]*n;d=[0]*n
for i in range(n):p[i]=l[i]+p[i-2];d[i]=max(p[i-1]if(i&1)else d[i-1],l[i]+d[i-2])
print(d[-1])

Solution (Python):
n=int(input());l=list(map(int,input().split()));p=[0]*n;d=[0]*n;p[0]=l[0]
for i in range(1,n):p[i]=l[i]+p[i-2];d[i]=max(p[i-1]if(i&1)else d[i-1],l[i]+d[i-2])
print(d[-1])

Solution (Python):
n=int(input());l=list(map(int,input().split()));p=[0]*n;d=[0]*n;p[0]=l[0]
for i in range(1,n):p[i]=l[i]+p[i-2];d[i]=max(p[i-1]if(i&1)else d[i-1],l[i]+(d[i-2]if i>1else 0))
print(d[-1])

Solution (Python):
n=int(input());l=list(map(int,input().split()));p=[0]*n;d=[0]*n;p[0]=l[0]
for i in range(1,n):p[i]=l[i]+(p[i-2]if i>1else 0);d[i]=max(p[i-1]if(i&1)else d[i-1],l[i]+(d[i-2]if i>1else 0))
print(d[-1])

Solution (Python):
n=int(input());l=list(map(int,input().split()));p=[0]*n;d=[0]*n
for i in range(n):p[i]=l[i]+(p[i-2]if i>1else 0)
for i in range(1,n):
  d[i]=p[i-1]if(i&1)else d[i-1]
  d[i]=max(d[i],l[i]+(d[i-2]if i>1else 0))
print(d[-1])

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

if N%2==0:
    dp = [[0]*2 for _ in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    
    for i in range(2, N):
        if i==2:
            dp[i][0] = dp[i-2][0]+A[i]
        else:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-3][0]+A[i], dp[i-2][1]+A[i])
    
    print(max(dp[N-2][0], dp[N-1][1]))
else:
    dp = [[0]*3 for _ in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    
    for i in range(2, N):
        if i==2:
            dp[i][0] = dp[i-2][0]+A[i]
        elif i==3:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-2][1]+A[i], dp[i-3][0]+A[i])
        else:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-3][0]+A[i], dp[i-2][1]+A[i])
            dp[i][2] = max(dp[i-4][0]+A[i], dp[i-3][1]+A[i], dp[i-2][2]+A[i])
    
    print(max(dp[N-3][0], dp[N-2][1], dp[N-1][2]))

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

def solve(n,a):
    wa=0
    for i in range(n):
        if(i%2==0):
            wa+=a[i]
    kotae=wa
    for i in range(n//2):
        wa+=a[(n//2-i-1)*2+1]
        wa-=a[(n//2-i-1)*2]
        if(wa>kotae):
            kotae=wa
    return kotae

def dfs(n,a,k):
    global zen
    zen.append([n,k])
    if(k==1):
        return max(a)
    ari=a[n-1]+dfs(n-2,a[:n-2],k-1)
    if(n==k*2-1):
        return ari
    nasi=dfs(n-1,a[:n-1],k)
    return max(ari,nasi)

n=int(input())

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

if(n%2==0):
    print(solve(n,a))
else:
    data=[[a[0],a[0]],[max(a[:2]),max(a[:2])]]
    
    data.append([max(a[:3]),a[0]+a[2]])
    for i in range(3,n):
        if(i%2==1):
            ari=a[i]+data[i-2][0]
            nasi=data[i-1][1]
            saiyo=max(ari,nasi)
            data.append([saiyo,saiyo])
        else:
            ooi=a[i]+data[i-2][1]
            nasi=data[i-1][1]
            ari=a[i]+data[i-2][0]
            sukunai=max(ari,nasi)
            data.append([sukunai,ooi])
    print(data[n-1][0])

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

dp = [{} for _ in range(N + 2)]
dp[0][0] = 0
dp[-1][0] = 0

for i in range(1, N + 1):
    f = (i - 1) // 2
    t = (i + 1) // 2
    for j in range(f, t + 1):
        var1 = dp[i - 2][j - 1] + A[i - 1] if j - 1 in dp[i - 2] else -float('inf')
        var2 = dp[i - 1][j] if j in dp[i - 1] else -float('inf')
        dp[i][j] = max(var1, var2)

print(dp[N][N // 2])

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

dp = [{} for _ in range(N + 2)]
dp[0][0] = 0
dp[-1][0] = 0

for i in range(1, N + 1):
    f = (i - 1) // 2
    t = (i + 1) // 2
    for j in range(f, t + 1):
        var1 = dp[i - 2][j - 1] + A[i - 1] if j - 1 in dp[i - 2] else -float('inf')
        var2 = dp[i - 1][j] if j in dp[i - 1] else -float('inf')
        dp[i][j] = max(var1, var2)

print(dp[N][N // 2])

Solution (Python):
n=int(input())
arr=list(map(int,input().split()))
if n%2==0:
  ans=-10**18
  dp=[[0]*2 for _ in range(n+10)]
  for i in range(n):
    dp[i+1][0]=dp[i-1][0]+arr[i]
    dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
  ans=max(ans,dp[n-1][0],dp[n][1])
  dp=[[0]*2 for _ in range(n+10)]
  for i in range(1,n):
    dp[i+1][0]=dp[i-1][0]+arr[i]
    dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
  ans=max(ans,dp[n][0])
  print(ans)
else:
  ans=-10**18
  dp=[[0]*3 for _ in range(n+10)]
  for i in range(n):
    dp[i+1][0]=dp[i-1][0]+arr[i]
    dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
    dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
  ans=max(ans,dp[n-2][0],dp[n-1][1],dp[n][2])
  dp=[[0]*3 for _ in range(n+10)]
  for i in range(1,n):
    dp[i+1][0]=dp[i-1][0]+arr[i]
    dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
    dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
  ans=max(ans,dp[n-1][0],dp[n][1])
  dp=[[0]*3 for _ in range(n+10)]
  for i in range(2,n):
    dp[i+1][0]=dp[i-1][0]+arr[i]
    dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
    dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
  ans=max(ans,dp[n][0])
  print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
dp = [{} for _ in range(N+1)]
INF = -float('inf')
for i in range(1,N+1):
    mid = i//2
    dp[i][mid-2],dp[i][mid-1],dp[i][mid],dp[i][mid+1],dp[i][mid+2]=INF,INF,INF,INF,INF
dp[1][1] = A[0]
dp[2][1] = max(A[1],dp[1][1])
dp[1][0],dp[2][0]=0,0

for i in range(2,N):
  a = A[i]
  ma = (i+2)//2
  mi = i//2
  dp[i+1][ma] = max(dp[i][ma],dp[i-1][ma-1]+a)
  dp[i+1][mi] = max(dp[i][mi],dp[i-1][mi-1]+a)

print(dp[-1][N//2])

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

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

Solution (Python):
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json

import bisect
import sys
import math
import bisect
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    A = [int(a) for a in input().split()]

    @lru_cache(None)
    def f(i, j):
        if i < 0 or j < 0:
            return -INF
        if i == 0:
            return -INF
        if abs(j - i // 2 - 1) >= 2:
            return -INF
        if j == 0:
            return 0
        if j == 1:
            return max(A[:i])
        return max(A[i - 1] + f(i - 2, j - 1), f(i - 1, j))

    print(f(N, math.floor(N / 2)))


if __name__ == "__main__":
    main()

Solution (Python):
import sys

n = int(input())
A = [int(_) for _ in input().split()]

if n == 1 or n == 2 or n == 3:
    print(max(A))
    sys.exit()

dp = [[0, 0] for j in range(n)]
M = - float('inf')
for i in range(4):
    M = max(M, A[i])
    dp[i][0] = M
dp[2][1] = dp[0][0] + A[2]
dp[3][1] = max(dp[1][0] + A[3], dp[2][1])

for i in range(4, n):
    for j in range(2):
        if i % 2 == 0 and j == 1:
            dp[i][j] = dp[i-2][1] + A[i]
        elif i % 2 == 0 and j == 0:
            dp[i][j] = max(dp[i-2][0] + A[i], dp[i-1][1])
        elif i % 2 == 1 and j == 1:
            dp[i][j] = max(dp[i-2][1] + A[i], dp[i-1][1])
        else:
            dp[i][j] = max(dp[i-2][0] + A[i], dp[i-1][0])

print(dp[n-1][(n+1)%2])

Solution (Python):
import sys

n = int(input())
A = [int(_) for _ in input().split()]



if n == 1 or n == 2 or n == 3:
    print(max(A))
    sys.exit()

dp = [[0, 0] for j in range(n)]
M = - float('inf')
for i in range(4):
    M = max(M, A[i])
    dp[i][0] = M
dp[2][1] = dp[0][0] + A[2]
dp[3][1] = max(dp[1][0] + A[3], dp[2][1])











            

for i in range(4, n):
    for j in range(2):
        
        if i % 2 == 0 and j == 1:
            dp[i][j] = dp[i-2][1] + A[i]
        elif i % 2 == 0 and j == 0:
            dp[i][j] = max(dp[i-2][0] + A[i], dp[i-1][1])
        elif i % 2 == 1 and j == 1:
            dp[i][j] = max(dp[i-2][1] + A[i], dp[i-1][1])
        else:
            dp[i][j] = max(dp[i-2][0] + A[i], dp[i-1][0])




print(dp[n-1][(n+1)%2])

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
if n <= 3:
  print(max(a))
  exit()

a = tuple(a)
dp = [[-10**15]*3 for i in range(n)]

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

Solution (Python):
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
  exit()
lim=n%2+2
dp=[[0]*lim for _ in range(n+1)]
for i in range(n):
  dp[i+1][0]=dp[i-1][0]+arr[i]
  dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
  if lim==3:
    dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
print(max(dp[-1][:lim]))

Solution (Python):
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
  exit()
lim=n%2+2
dp=[[0]*lim for _ in range(n+1)]
for i in range(n):
  dp[i+1][0]=dp[i-1][0]+arr[i]
  dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
  if lim==3:
    dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
print(max(dp[-1][:lim]))

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
if n <= 3:
  print(max(a))
  exit()

a = tuple(a)
dp = [[-10**15]*3 for i in range(n)]

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

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



def main():
    N = I()
    a = LI()
    dp = [0] * N
    dp[1] = max(a[0], a[1])
    c = a[0]

    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])


if __name__ == '__main__':
    main()

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

le, lo, re, ro = [0], [0], [0], [0]

for i in range(n):
    if i % 2 == 0:
        le.append(le[-1] + a[i])
    else:
        lo.append(lo[-1] + a[i])

for i in range(n-1, -1, -1):
    if i % 2 == 0:
        re.append(re[-1] + a[i])
    else:
        ro.append(ro[-1] + a[i])

le_o = [0]
for i in range(len(lo)-1):
    le_o.append(max(0, le_o[-1] + a[2*i+1] - a[2*i]))


if n % 2 == 0:
    n //= 2
    ans = lo[n]
    for i in range(0, n + 1):
        ans = max(ans, le[i] + ro[n-i])

    print(ans)

else:
    n //= 2
    ans = le[n]
    for i in range(0, n+1):
        ans = max(ans, le[i] + ro[n-i])
        ans = max(ans, lo[i] + re[n-i])
        ans = max(ans, le[i] + re[n-i] + le_o[i])

    print(ans)

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

dp = [0] * (n+1)
dp[2] = max(A[0], A[1])
s = A[0]

for i, a in enumerate(A, 1):
    if i <= 2:
        continue
    if i%2:  
        dp[i] = max(dp[i-1], a+dp[i-2])
        s += a
    else:  
        dp[i] = max(a+dp[i-2], s)


print(dp[-1])

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

B = [[0] * 2 for i in range(300000)]
for i in range(N):
    if i == 0:
        B[0][0] = 0
        B[0][1] = A[0]
    elif i == 1:
        B[1][0] = 0
        B[1][1] = max([A[0], A[1]])
    elif i % 2 == 0:
        B[i][0] = max([B[i-2][0] + A[i], B[i-1][1]])
        B[i][1] = B[i-2][1] + A[i]
    else:
        B[i][0] = max([B[i-2][0] + A[i], B[i-1][0]])
        B[i][1] = max([B[i-2][1] + A[i], B[i-1][1]])

if i % 2 == 0:
    print(B[N-1][0])
else:
    print(B[N-1][1])

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
s = [0]*N
for i in range(N):
    s[i] = s[i-2]+A[i]

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

print(dp[-1])

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    dp = [[0,0] for _ in range(N+1)]
    dp[2] = [A[0],A[1]]
    
    for i in range(2,N):
        if (i+1)%2 ==0:
            dp[i+1][0] = dp[i-1][0]+A[i-1]
        else:
            dp[i+1][0] = max(dp[i])

        dp[i+1][1] = max(dp[i-1])+A[i]

    print(max(dp[N]))
    return


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):
def main():
    from collections import defaultdict

    inf = 10 ** 15

    N = int(input())
    *a, = map(int, input().split())

    it = iter(a)

    dp = [defaultdict(lambda: -inf) for _ in range(N + 1)]
    dp[0][0] = 0
    dp[1][0] = 0
    dp[1][1] = next(it)
    for i, x in enumerate(it, 2):
        mi = (i - 1) // 2
        ma = (i + 1) // 2
        for taken_count in range(mi, ma + 1):
            dp[i][taken_count] = max(
                dp[i - 1][taken_count],
                dp[i - 2][taken_count - 1] + x
            )

    ans = dp[N][N // 2]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input().strip())
A = list(map(int, input().strip().split()))

if N % 2 == 0:
  dp = [[0 for _ in range(N)] for _ in range(2)]
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  for i in range(2, N):
    if i % 2 == 0:
      dp[0][i] = dp[0][i-2] + A[i]
    else:
      dp[1][i] = max(dp[1][i-2], dp[0][i-3]) + A[i]
  print(max(dp[-1][-1], dp[-2][-2]))
else:
  dp = [[0 for _ in range(N)] for _ in range(3)]
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  dp[2][2] = A[2]
  for i in range(2, N):
    if i % 2 == 0:
      dp[0][i] = dp[0][i-2] + A[i]
      dp[2][i] = max(dp[0][i-4], dp[1][i-3], dp[2][i-2]) + A[i]
    else:
      dp[1][i] = max(dp[1][i-2], dp[0][i-3]) + A[i]
  print(max(dp[-1][-1], dp[-2][-2], dp[-3][-3]))

Solution (Python):
def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    inf = -10**16
    if n%2:
        dp0 = [0]*n
        dp1 = [0]*n
        sumk = a[0]
        dp0[1] = inf
        dp1[1] = max([a[0], a[1]])
        if n > 2:
            dp0[2] = 0
            dp1[2] = max([a[2], dp1[1]])
            sumk += a[2]
        if n > 3:
            dp0[3] = max([dp1[2], a[3]])
            dp1[3] = max([a[0]+a[2], a[0]+a[3], a[1]+a[3]])
        for i in range(4, n):
            if i%2 == 0:
                dp0[i] = max([dp0[i-1], dp0[i-2]+a[i]])
                dp1[i] = max([dp1[i-1], dp1[i-2]+a[i]])
                sumk += a[i]
            else:
                dp0[i] = max([dp1[i-1], dp0[i-2]+a[i]])
                dp1[i] = max([dp1[i-2]+a[i], sumk])
        ans = dp1[n-1]
    else:
        key = sum(a[::2])
        ans = key
        for i in range(n-1, 0, -2):
            key += a[i]
            key -= a[i-1]
            if ans < key:
                ans = key
    print(ans)
            
    
    

if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)
def solve(pick, idx):

    if pick == 0: return 0
    if idx >= n: return -float('inf')
    if (pick, idx) in dp: return dp[pick, idx]
    if n-idx+2 < pick*2: return -float('inf')
    total = max(A[idx] + solve(pick-1, idx+2), solve(pick, idx+1))

    dp[(pick, idx)] = total
    return total

n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n//2

print(solve(pick, 0))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
inf = 10 ** 16
if N % 2:
  dp = [[-inf] * 3 for _ in range(N + 2)]
  dp[0][0] = 0
  dp[1][1] = 0
  dp[2][2] = 0
  if N > 4: dp[4][2] = a[0]
  for i in range(N):
    for j in range(3):
      if dp[i][j] == -inf: continue
      if i + 2 <= N + 1: dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i])
      if i + 3 <= N + 1 and (j < 2): dp[i + 3][j + 1] = max(dp[i + 3][j + 1], dp[i][j] + a[i])
      if i + 4 <= N + 1 and (j == 0): dp[i + 4][j + 1] = max(dp[i + 4][j + 1], dp[i][j] + a[i])
  print(max(dp[-1][-1], dp[-2][-2], dp[-3][-3]))
  
else:
  dp = [[-inf] * 2 for _ in range(N + 2)]
  dp[0][0] = 0
  dp[1][1] = 0
  for i in range(N):
    for j in range(2):
      if dp[i][j] == -inf: continue
      if i + 2 <= N + 1: dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i])
      if i + 3 <= N + 1 and (j < 1): dp[i + 3][j + 1] = max(dp[i + 3][j + 1], dp[i][j] + a[i])
  print(max(dp[-1][-1], dp[-2][-2]))

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

dp = [0] * (N + 1)
dp[2] = max(A[0], A[1])
s = A[0]
for i, a in enumerate(A, 1):
  if i <= 2:
    continue
  if i%2: 
    dp[i] = max(dp[i-1], a+dp[i-2])
    s += a
  else: 
    dp[i] = max(a+dp[i-2], s)

print(dp[-1])

Solution (Python):
N=int(input())

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


if N<=3:
  print(max(A))
  exit(0)






if N&1:
  
  dp=[[-((10**9) * (10**5))-1]*3 for i in range(N)]

  dp[0][0] = A[0] 
  dp[1][1] = A[1] 
  dp[2][2] = A[2] 
  for i in range(N):
    if i+2<N:
      
      for j in range(3):
        if dp[i+2][j] < dp[i][j] + A[i+2]:
          dp[i+2][j] = dp[i][j] + A[i+2]
    if i+3<N:
      
      for j in range(2):
        if dp[i+3][j+1] < dp[i][j] + A[i+3]:
          dp[i+3][j+1] = dp[i][j] + A[i+3]
    if i+4<N:
      
      if dp[i+4][2] < dp[i][0] + A[i+4]:
        dp[i+4][2] = dp[i][0] + A[i+4]
  
  
  
  
  
  ans = max(dp[N-3][0],dp[N-2][1],dp[N-1][2])
  print(ans)
  
else:
  
  
  dp=[[-((10**9) * (10**5))-1]*2 for i in range(N)]

  dp[0][0] = A[0] 
  dp[1][1] = A[1] 
  for i in range(N):
    if i+2<N:
      
      for j in range(2):
        if dp[i+2][j] < dp[i][j] + A[i+2]:
          dp[i+2][j] = dp[i][j] + A[i+2]
    if i+3<N:
      
      if dp[i+3][1] < dp[i][0] + A[i+3]:
        dp[i+3][1] = dp[i][0] + A[i+3]
  
  
  
  
  ans = max(dp[N-2][0],dp[N-1][1])
  print(ans)

Solution (Python):
import sys












readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = [0] + list(map(int, readline().split()))

    if n == 2:
        print(max(a[1],a[2]))
        sys.exit()

    dp = [[0] * 2 for _ in range(n + 1)]

    
    dp[1][0] = 0
    dp[2][0] = max(a[1], a[2])
    dp[3][0] = max(a[1], a[2], a[3])

    
    dp[1][1] = a[1]
    dp[3][1] = a[1] + a[3]

    i = 4

    while i < n + 1:
        cur1 = a[i]

        
        dp[i][0] = max(dp[i - 1][1], dp[i - 2][0] + cur1)

        if i == n:
            break

        i += 1
        cur2 = a[i]

        
        dp[i][0] = max(dp[i - 2][0] + cur2, dp[i - 3][0] + cur2, dp[i - 1][0], dp[i - 2][1])
        dp[i][1] = dp[i - 2][1] + cur2

        i += 1

    print(dp[n][0])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n % 2 == 0:
        dp = [[-10**18]*2, [-10**18]*2]
        dp[0][0] = 0
        for i in range(n):
            dp2 = [[-10**18]*2, [-10**18]*2]
            
            dp2[1][0] = max(dp2[1][0], dp[0][0]+a[i])
            dp2[1][1] = max(dp2[1][1], dp[0][1]+a[i])
            
            dp2[0][1] = max(dp2[0][1], dp[0][0])
            
            dp2[0][0] = max(dp2[0][0], dp[1][0])
            dp2[0][1] = max(dp2[0][1], dp[1][1])
            dp = dp2
        print(max(dp[1][1], dp[0][0]))
        return
    dp = [[-10**18]*3, [-10**18]*3]
    dp[0][0] = 0
    for i in range(n):
        
        dp2 = [[-10**18]*3, [-10**18]*3]
        dp2[1][0] = max(dp2[1][0], dp[0][0]+a[i])
        dp2[1][1] = max(dp2[1][1], dp[0][1]+a[i])
        dp2[1][2] = max(dp2[1][2], dp[0][2]+a[i])
        
        dp2[0][1] = max(dp2[0][1], dp[0][0])
        dp2[0][2] = max(dp2[0][2], dp[0][1])
        
        dp2[0][0] = max(dp2[0][0], dp[1][0])
        dp2[0][1] = max(dp2[0][1], dp[1][1])
        dp2[0][2] = max(dp2[0][2], dp[1][2])
        dp = dp2
    print(max(dp[1][2], dp[0][1]))


main()

Solution (Python):







import sys
from functools import lru_cache

sys.setrecursionlimit(10**9)

Input = lambda: sys.stdin.readline().rstrip()
IntRead = lambda: int(Input())
LineRead = lambda: list(map(int, Input().split()))

def main():
    N = IntRead()
    INF = 10**18
    nums = LineRead()
    @lru_cache(None)
    def dp(idx, n):
        if idx >= N:
            return -INF
        if N - idx + 2 < 2 * n:
            return -INF
        if n == 0:
            return 0
        elif n == 1:
            return max(nums[idx:])
        return max(nums[idx] + dp(idx + 2, n - 1), dp(idx + 1, n))
    print(dp(0, N // 2))


if __name__ == "__main__":
    main()

Solution (Python):

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if N - index + 1 < 2 * n:
        return -INF
    if N - index - 2 > 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
if N==2:
    print(max(A))
elif N==3:
    print(max(A))
else:
    if N%2==1:
        dp=[[0 for i in range(0,3)] for i in range(0,N)]
        dp[0][2]=A[0]
        dp[0][1]=-float('inf')
        dp[0][0]=-float('inf')
        dp[1][2]=-float('inf')
        dp[1][1]=A[0]
        dp[1][0]=-float('inf')

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

        test1=dp[N-1][0]

        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][1]=A[1]
        dp[1][0]=-float('inf')

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

        test2=dp[N-1][0]

        A=A[::-1]
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][1]=A[1]
        dp[1][0]=-float('inf')

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

        test3=dp[N-1][0]

        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3,test4))

    if N%2==0:
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=A[0]

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

        test1=dp[N-1][0]

        test3=sum(A[i] for i in range(0,N) if i%2==0)
        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test3,test4))

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

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

Solution (Python):
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    if n % 2 == 0:
        if n == 2:
            print(max(a))
            return
        v = [[None for j in range(2)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        for i in range(2, n):
            for j in range(2):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j >= 1 and i >= 3:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(2) if v[n-1][j] is not None]
        print(max(c))
    else:
        if n == 3:
            print(max(a))
            return
        v = [[None for j in range(3)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][0] = a[0]+a[2]
        v[2][2] = a[2]
        for i in range(3, n):
            for j in range(3):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j >= 1:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if j >= 2 and i >= 4:
                    if v[i-4][j-2] is not None:
                        c.append(v[i-4][j-2])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(1, 3) if v[n-1][j] is not None]
        print(max(c))


def input(): return stdin.readline().rstrip()


main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

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

a_cs = [0] * (n + 1)
a_cs[-2] = a[-1]
for i in reversed(range(n - 1)):
    a_cs[i] = a[i] + a_cs[i + 2]


d = {}


def func(i):
    if i == n:
        return 0
    if i == n - 1:
        return a[-1]
    if i in d:
        return d[i]

    m = n - i
    if m % 2 == 0:
        ans0 = a[i] + func(i + 2)
        ans1 = a_cs[i + 1]
        ans = max(ans0, ans1)
    else:
        ans0 = a[i + 0] + func(i + 2)
        ans1 = a[i + 1] + func(i + 3)
        ans2 = a_cs[i + 2]
        ans = max(ans0, ans1, ans2)

    d[i] = ans
    return ans


ans = func(0)

print(ans)