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 = int(input())
A = list(map(int, input().split()))
if N % 2 == 0:
    NINF = -(10 ** 16)
    dp = [[NINF for j in range(2)] for i in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    for i in range(N):
        if i - 2 >= 0:
            if dp[i - 2][0] != NINF:
                dp[i][0] = dp[i - 2][0] + A[i]
            if dp[i - 2][1] != NINF:
                dp[i][1] = dp[i - 2][1] + A[i]
        if i - 3 >= 0:
            dp[i][1] = max(dp[i][1], dp[i - 3][0] + A[i])

    res = max(dp[N - 1][1], dp[N - 2][0])
else:
    NINF = -(10 ** 16)
    dp = [[NINF for j in range(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 >= 0:
            if dp[i - 2][0] != NINF:
                dp[i][0] = dp[i - 2][0] + A[i]
            if dp[i - 2][1] != NINF:
                dp[i][1] = dp[i - 2][1] + A[i]
            if dp[i - 2][2] != NINF:
                dp[i][2] = dp[i - 2][2] + A[i]
        if i - 3 >= 0:
            dp[i][1] = max(dp[i][1], dp[i - 3][0] + A[i])
            dp[i][2] = max(dp[i][2], dp[i - 3][1] + A[i])
        if i - 4 >= 0:
            dp[i][2] = max(dp[i][2], dp[i - 4][0] + A[i])

    res = max(dp[N - 1][2], dp[N - 2][1], dp[N - 3][0])

print(res)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
from collections import deque
q=deque([(-1,0,-2,0)])
ans=-10**18
for i,a in enumerate(A):
    d={}
    while q and q[0][0]<i:
        j,n,r,x=q.popleft()
        if r<-1:
            if n==N//2-1:
                ans=max(ans,x+a)
            elif n not in d:
                d[n]=x
            elif d[n]<x:
                d[n]=x
        if (j+1)//2<=n:
            q.append((i,n,r-1,x))
    for n,x in d.items():
        q.append((i,n+1,-1,x+a))
print(ans)

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


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

a0=[a[0],a[0]]
a1=[0,a[1]]
a2=[0,0,a[2]]
for i in range(2,n):
    if i%2==0:
        a0.append(a0[i-2]+a[i])
        a1.append(a1[i-1])
        if i>=4: a2.append(max(a2[i-2],a1[i-3],a0[i-4])+a[i])
    else:
        a0.append(a0[i-1])
        a1.append(max(a1[i-2],a0[i-3])+a[i])
        a2.append(a2[i-1])

if n%2==1: print(max(a0[n-1],a1[n-1],a2[n-1]))
else: print(max(a0[n-1],a1[n-1]))

Solution (Python):
import os

import itertools
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7





def test(N, A):
    ret = -INF
    for choices in itertools.combinations(range(N), N // 2):
        ok = True
        for i, j in zip(choices, choices[1:]):
            if abs(i - j) == 1:
                ok = False
                break
        if ok:
            s = 0
            for i in choices:
                s += A[i]
            ret = max(ret, s)
    print(ret)


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
N = len(A)

if N % 2 == 0:
    cum0 = list(itertools.accumulate([0] + A[::2]))
    cum1 = list(itertools.accumulate([0] + A[1::2]))
    ans = -INF
    for i in range(len(cum0)):
        s = cum1[-1] - cum1[i] + cum0[i]
        ans = max(s, ans)
    print(ans)
    exit()

cnt = 2 if N % 2 == 1 else 1

dp = [[-INF] * (cnt + 1) for _ in range(N + 2)]
for i in range(cnt + 1):
    dp[i][i] = 0
for i in range(N):
    for j in range(cnt + 1):
        for k in range(cnt + 1):
            if i + 2 + k < len(dp) and j + k < len(dp[0]):
                dp[i + 2 + k][j + k] = max(dp[i + 2 + k][j + k], dp[i][j] + A[i])
print(dp[-1][-1])

Solution (Python):
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline
    from collections import Counter

    import random

    n = int(input())
    aa = list(map(int, input().split()))
    if n%2 == 0:
        dp = [[0]*n for _ in range(2)]
        dp[0][0] = aa[0]
        dp[1][1] = aa[1] if aa[1]>aa[0] else aa[0]
        for i in range(2, n, 2):
            aa_i = aa[i]
            dp[0][i] = dp[0][i-2]+ aa_i

            aa_i_p_1 = aa[i+1]
            dp_i_1 = dp[1][i-1]
            next = (dp_i_1+aa_i_p_1) if (dp_i_1+aa_i_p_1 > dp[0][i]) else dp[0][i]
            dp[1][i+1] = next
        print(dp[1][n-1])

    else:
        dp = [[0]*n for _ in range(3)]
        dp[0][0] = aa[0]
        dp[1][1] = aa[1] if aa[1]>aa[0] else aa[0]
        for i in range(2, n, 2):
            aa_i = aa[i]
            dp[0][i] = dp[0][i-2]+ aa_i
            dp_i_2 = dp[2][i-2]
            dp[2][i] = dp_i_2+aa_i if dp_i_2+aa_i > dp[1][i-1] else dp[1][i-1]

            if i == n-1:
                break
            aa_i_p_1 = aa[i+1]
            dp_i_1 = dp[1][i-1]
            dp[1][i+1] = dp_i_1+aa_i_p_1 if dp_i_1+aa_i_p_1 > dp[0][i] else dp[0][i]
        print(dp[2][n-1])

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

if(n <= 3):
    print(max(a))
    exit()

left = [0] * (n+1)
right = [0] * (n+1)

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

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

ans = left[-1]
for i in range(0,n-1 ):
    ans = max(ans, left[i] + right[i+2])

if(n%2==0):
    print(left[-1])
else:
    print(ans)

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

INF = 10**17

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

dp = [[-INF]*3 for _ in range(N)]

for i, a in enumerate(A):
    if i == 0:
        dp[i][2] = a
    elif i == 1:
        dp[i][0] = max(a, dp[i-1][1])
    elif i == 2:
        dp[i][1] = a
        dp[i][2] = dp[0][2] + a
    elif (i+1)%2 == 0:
        dp[i][0] = max(dp[i-3][2], dp[i-2][0]) + a
    else:
        dp[i][1] = max([dp[i-4][2], dp[i-3][0], dp[i-2][1]]) + a
        dp[i][2] = dp[i-2][2] + a

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

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**16
    n=II()
    aa=LI()
    if n%2:
        dp=[[-inf]*3 for _ in range(n)]
        dp[0][2]=0
        dp[0][0]=aa[0]
        dp[1][1]=aa[1]
        for i,a in enumerate(aa[2:],1):
            if i-1>=0:dp[i+1][0]=dp[i-1][0]+a
            if i-2>=0:dp[i+1][1]=max(dp[i-2][0],dp[i-1][1])+a
            elif i-1>=0:dp[i+1][1]=dp[i-1][1]+a
            if i-3>=0:dp[i+1][2]=max(dp[i-3][0],dp[i-2][1],dp[i-1][2])+a
            elif i - 2 >= 0: dp[i + 1][2] = max(dp[i - 2][1], dp[i - 1][2]) + a
            elif i - 1 >= 0: dp[i + 1][2] = dp[i - 1][2] + a
        ans=max(dp[-1][2],dp[-2][1])
        if n>2:ans=max(ans,dp[-3][0])
    else:
        dp=[[-inf]*2 for _ in range(n)]
        dp[0][0]=aa[0]
        dp[1][1]=aa[1]
        for i,a in enumerate(aa[2:],1):
            dp[i+1][0]=dp[i-1][0]+a
            if i-2>=0:dp[i+1][1]=max(dp[i-2][0],dp[i-1][1])+a
            elif i - 1 >= 0: dp[i + 1][1] = dp[i - 1][1] + a
        ans=max(dp[-1][1],dp[-2][0])
    print(ans)

main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

SUM=[0]*(N+1)
for i in range(N-1,-1,-1):
    SUM[i]=SUM[i+1]

    if (N-i)%2==1:
        SUM[i]+=A[i]



ADICT=dict()

def calc(i,select):
    if ADICT.get((i,select))!=None:
        return ADICT.get((i,select))
    rest=N-i

    if rest==0 or select==0:
        ADICT[(i,select)]=0
        return 0

    if rest%2==1 and rest//2+1==select:
        ADICT[(i,select)]=SUM[i]
        return SUM[i]
    
    elif rest%2==0 and rest//2==select:
        ADICT[(i,select)]=max(calc(i+1,select),A[i]+calc(i+2,select-1))
        return ADICT[(i,select)]

    elif rest%2==1 and rest//2==select:
        ADICT[(i,select)]=max(calc(i+1,select),A[i]+calc(i+2,select-1))
        return ADICT[(i,select)]

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

SUM=[0]*(N+1)
for i in range(N-1,-1,-1):
    SUM[i]=SUM[i+1]

    if (N-i)%2==1:
        SUM[i]+=A[i]



ADICT=dict()

def calc(i,select):
    if ADICT.get((i,select))!=None:
        return ADICT.get((i,select))
    rest=N-i

    if rest==0 or select==0:
        ADICT[(i,select)]=0
        return 0

    if rest%2==1 and rest//2+1==select:
        ADICT[(i,select)]=SUM[i]
        return SUM[i]
    
    elif rest%2==0 and rest//2==select:
        ADICT[(i,select)]=max(calc(i+1,select),A[i]+calc(i+2,select-1))
        return ADICT[(i,select)]

    elif rest%2==1 and rest//2==select:
        ADICT[(i,select)]=max(calc(i+1,select),A[i]+calc(i+2,select-1))
        return ADICT[(i,select)]

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

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

N = int(input())
A = list(map(int, input().split()))
odd = list(accumulate([0] + A[::2]))
even = list(accumulate([0] + A[::-1][::2]))
ans = max(odd[i] + even[N//2-i] for i in range(N//2+1))
if N % 2 == 1:
    dp = [0] * (N//2+1)
    for i in range(0, N-1, 2):
        dp[i//2+1] = max(odd[i//2+1], dp[i//2] + A[i+1])
    ans2 = max(dp[i] + even[N//2-i] for i in range(N//2+1))
    ans = max(ans, ans2)
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
dp = [[[-10**15, -10**15] for i in range(4)] for j in range(n+1)]


dp[0][0][0] = 0


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


ans = 0
if n % 2 == 0:
    ans = max(max(dp[n][0]), dp[n][1][1])
else:
    ans = max(max(dp[n][0]), max(dp[n][1]), dp[n][2][1])

print(ans)

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

Solution (Python):
from sys import stdin

input = stdin.readline

n = int(input())
a = [int(x) for x in input().split()]
dp = [[0] * 3 for x in range(n)]

dp[0][0] = a[0]
dp[1][1] = a[1]


if n > 2:
    dp[2][0] = a[0] + a[2]
    dp[2][2] = a[2]

if n > 3:
    dp[3][1] = max(a[0] + a[3], a[1] + a[3])

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


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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
if n%2 == 0:
  a.append(-float("inf"))
  n += 1
if n == 3:
  print(max(a))
  exit()
p0 = a[0]
z0 = -float("inf")
z1 = a[1]
y0 = a[0]+a[2]
y1 = -float("inf")
y2 = a[2]
x0 = -float("inf")
x1 = max(p0,z1)+a[3]
x2 = -float("inf")
for i in range(4,n-1):
  w0 = y0+a[i]
  w1 = max(y1,z0)+a[i]
  w2 = max(y2,z1,p0)+a[i]
  p0 = z0
  z0 = y0
  z1 = y1
  y0 = x0
  y1 = x1
  y2 = x2
  x0 = w0
  x1 = w1
  x2 = w2
w0 = y0+a[n-1]
w1 = max(y1,z0)+a[n-1]
w2 = max(y2,z1,p0)+a[n-1]
print(max(y0,x1,w2))

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
dp[1] = max(A[0],A[1])
if N>=3:
    dp[2] = max(A[0],A[1],A[2])
for n in range(3,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],A[n-1]+dp[n-3],s[n-2])

print(dp[-1])

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
input = sys.stdin.readline
INF = 10**18

n = int(input())
a = [int(item) for item in input().split()]



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

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

ans = -INF
if n % 2 == 0:
    ans = max(dp[-1][1][1], ans)
    ans = max(dp[-1][0][0], ans)
else:
    ans = max(dp[-1][2][1], ans)
    ans = max(dp[-1][1][0], ans)
print(ans)

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

from functools import lru_cache

@lru_cache(None)
def dfs(p, remain):

    n = len(arr)

    if remain == 0 or p >= n:
        return 0

    if remain == 1:
        return max(arr[p:])
        
    len_remain = n - (p + 1)

    t = -float('inf')
    if (remain - 1) * 2 + 1 <= len_remain:
        t = dfs(p + 1, remain)

    t2 = arr[p] + dfs(p + 2, remain - 1)

    return max(t, t2)

    


n = int(input())

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

ans = dfs(0, n // 2)

print (ans)

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

if n == 2:
    print(max(a[0], a[1]))
    exit()
elif n == 3:
    ans = max(a[0], a[1])
    print(max(ans, a[2]))
    exit()

if n % 2 == 0:
    inf = - float('inf')
    dp = [[inf, inf] for _ in range(n)]
    dp[0][0] = a[0]
    dp[1][1] = a[1]
    dp[2][0] = a[0] + a[2]

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

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

inf = - float('inf')
dp = [[inf, inf, inf] for _ in range(n)]
dp[0][0] = a[0]
dp[1][1] = a[1]
dp[2][0] = a[0] + a[2]
dp[2][2] = a[2]
dp[3][1] = max(a[0], a[1]) + a[3]

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

ans = max(dp[n-1][2], dp[n-2][1])
print(max(ans, dp[n-3][0]))

Solution (Python):
from itertools import accumulate


def solve_odd(n, aaa):
    INF = 10 ** 18
    p0, p1, p2, a0, a1, a2 = INF, INF, INF, INF, INF, 0
    for a in aaa:
        n2 = min(INF, p2 + a)
        n1 = min(INF, a2 + a, p1 + a)
        n0 = min(INF, a1 + a, p0 + a)
        p0, p1, p2, a0, a1, a2 = a0, a1, a2, n0, n1, n2
    return sum(aaa) - min(p0, a1)


def solve_even(n, aaa):
    fwd = [0] + list(accumulate(aaa[::2]))
    bwd = [0] + list(accumulate(aaa[::-2]))
    bwd.reverse()
    return max(f + b for f, b in zip(fwd, bwd))


n = int(input())
aaa = list(map(int, input().split()))
if n % 2 == 0:
    print(solve_even(n, aaa))
else:
    print(solve_odd(n, aaa))

Solution (Python):
from sys import stdin
import sys


def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]






























	
	
def comp(n, aList):
	num=n//2
	score=[[None for _ in range(num)] for i in range(3)]

	
	for i in range(n):
		for j in range(max(0, num-(n-i)//2-1), min(i//2+1,num)):
			if j==0:
				if i==0:
					ns=aList[i]
				else:
					ns=max(aList[i], score[(i-1)%3][0])
			else:
				nextScore=[]
				if i>=1:
					s=score[(i-1)%3][j]
					if s is not None:
						nextScore.append(s)
				if i>=2:
					s=score[(i-2)%3][j-1]
					if s is not None:
						s+=aList[i]
						nextScore.append(s)
				if len(nextScore)>0:
					ns=max(nextScore)
			
			score[i%3][j]=ns
	

	
	print(score[(n-1)%3][-1])


def main():
	n=int(nextLine())
	aList=nextIntList()






	
	comp(n, aList)

	
	
if __name__=="__main__":
	main()

Solution (Python):
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    if n < 4:
        print(max(a))
        return
    odd = n % 2 == 1
    if odd:
        dp = [[0] * 3 for _ in range(n)]
    else:
        dp = [[0] * 2 for _ in range(n)]
    dp[0][0] = a[0]
    dp[1][1] = a[1]
    if odd:
        dp[2][2] = a[2]
    for i in range(2, n, 2):
        dp[i][0] = dp[i - 2][0] + a[i]
    for i in range(3, n, 2):
        dp[i][1] = max(dp[i - 2][1] + a[i], dp[i - 3][0] + a[i])
    if odd:
        for i in range(4, n, 2):
            dp[i][2] = max(dp[i - 2][2] + a[i], dp[i - 3]
                           [1] + a[i], dp[i - 4][0] + a[i])
    if odd:
        print(max(dp[-1][-1], dp[-2][-2], dp[-3][-3]))
    else:
        print(max(dp[-1][-1], dp[-2][-2]))


if __name__ == '__main__':
    resolve()

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

Solution (Python):
import math
import fractions



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''








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

imp = -999999999999999999

dp = [[-1e30,-1e30,-1e30,-1e30] for i in range(n)]


dp[0][0] = 0
dp[0][1] = imp
dp[0][2] = imp
dp[0][3] = a[0]
dp[1][0] = 0
dp[1][1] = dp[0][3]
dp[1][2] = imp
dp[1][3] = a[1]

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

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    if N % 2 == 0:
        if N == 2: print(max(A))
        else:
            DP = [[-10 ** 20, -10 ** 20] for _ in range(N)]
            DP[0][0] = A[0]
            DP[1][1] = A[1]
            for i in range(2, N):
                DP[i][0] = max(DP[i][0], DP[i-2][0] + A[i])
                DP[i][1] = max(DP[i][1], DP[i-2][1] + A[i])
                if i > 2: DP[i][1] = max(DP[i][1], DP[i-3][0] + A[i])
            print(max(DP[N-2][0], DP[N-1][1]))
    else:
        DP = [[-10**20, -10**20, -10**20] for _ in range(N)]
        DP[0][0] = A[0]
        DP[1][1] = A[1]
        DP[2][2] = A[2]
        DP[2][0] = A[0] + A[2]
        for i in range(3, N):
            DP[i][0] = max(DP[i-2][0] + A[i], DP[i][0])
            DP[i][1] = max(DP[i-2][1] + A[i], DP[i][1])
            DP[i][2] = max(DP[i-2][2] + A[i], DP[i][2])
            if i > 2: 
                DP[i][1] = max(DP[i][1], DP[i-3][0] + A[i])
                DP[i][2] = max(DP[i][2], DP[i-3][1] + A[i])
        ans = max(DP[N-1][2], DP[N-2][1])
        ans = max(ans, DP[N-3][0])

        print(ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
n = int(input())
s = list(map(int,input().split()))
ans = -1000000000000000
dp = [{} for _ in range(n)]
dp[0][1] = s[0]
dp[1][1] = s[1]
if n >= 3:
    dp[2][1] = s[2]
for i in range(n):
    for x in dp[i].keys():
        y = dp[i][x]
        if x == n//2:
            ans = max(ans,y)
        else:
            if (n-(i+2)+1)//2 >= n//2-(x+1) and i+2 <= n-1:
                if x+1 in dp[i+2].keys():
                    dp[i+2][x+1] = max(dp[i+2][x+1],dp[i][x] + s[i+2])
                else:
                    dp[i+2][x+1] = dp[i][x] + s[i+2]
            if (n-(i+3)+1)//2 >= n//2-(x+1) and i+3 <= n-1:
                if x+1 in dp[i+3].keys():
                    dp[i+3][x+1] = max(dp[i+3][x+1],dp[i][x] + s[i+3])
                else:
                    dp[i+3][x+1] = dp[i][x] + s[i+3]
            if (n-(i+4)+1)//2 >= n//2-(x+1) and i+4 <= n-1:
                if x+1 in dp[i+4].keys():
                    dp[i+4][x+1] = max(dp[i+4][x+1],dp[i][x]+s[i+4])
                else:
                    dp[i+4][x+1] = dp[i][x]+s[i+4]
print(ans)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    if not n&1:
        dp = a[:2]
        for i in range(2,n)[::2]:
            nd = [-float("inf")]*2
            nd[0] = dp[0]+a[i]
            nd[1] = max(dp)+a[i+1]
            dp = [j for j in nd]
        print(max(dp))
        return
    dp = a[:3]
    dp[0] = a[0]
    dp[1] = a[1]
    dp[2] = a[2]
    for i in range(2,n-1)[::2]:
        nd = [-float("inf")]*3
        nd[0] = dp[0]+a[i]
        nd[1] = max(dp[0],dp[1])+a[i+1]
        nd[2] = max(dp)+a[i+2]
        dp = [j for j in nd]
    print(max(dp))
    return


if __name__ == "__main__":
    solve()

Solution (Python):

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

if N % 2 == 0:
    dp = [[[0, 0] for j in range(2)] for i in range(N)]

    for i, a in enumerate(aa):
        dp[i][0][1] = dp[i - 1][0][0] + a
        dp[i][0][0] = dp[i - 1][0][1]

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

    print(max(max(dp[-1][0]), dp[-1][1][1]))
else:
    dp = [[[0, 0] for j in range(3)] for i in range(N)]

    for i, a in enumerate(aa):
        dp[i][0][1] = dp[i - 1][0][0] + a
        dp[i][0][0] = dp[i - 1][0][1]

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

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

    print(max(max(dp[-1][1]), dp[-1][2][1]))

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
a = nl()
dp = [[0]*3 for _ in range(n+5)]
t = n%2
for i in range(n):
    dp[i][0] = dp[i-2][0] + a[i]
    dp[i][1] = max(dp[i-2][1], dp[i-3][0]) + a[i]
    if t:
        dp[i][2] = max(dp[i-2][2], dp[i-3][1], dp[i-4][0]) + a[i]
if t:
    print(max(dp[n-3][0], dp[n-2][1], dp[n-1][2]))
else:
    print(max(dp[n-2][0], dp[n-1][1]))

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
if n%2 == 0:
    dmax = 0
    ans = sum(A[::2])
    d = [0]*(n//2 + 1)
    for i in range(n//2):
        d[i+1] = d[i] + A[-2*i-1] - A[-2*i-2]
        dmax = max(dmax, d[i+1])
    print(ans + dmax)
else:
    d1 = [0]*(n//2 + 1)
    d1max = [0]*(n//2 + 1)
    d2 = [0]*(n//2 + 1)
    d2max = 0
    ans = sum(A[:-2:2])
    for i in range(n//2):
      d1[i+1] = d1[i] + A[-2*i-1] - A[-2*i-2]
      d1max[i+1] = max(d1max[i], d1[i+1])
      d2[i+1] = d2[i] + A[-2*i-2] - A[-2*i-3]
      d2max = max(d2max, d2[i+1] + d1max[i+1])
    print(ans + d2max)

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

ans = sum(A[1::2])
dA = []
for a1, a2 in zip(A, A[1:]):
    dA.append(a1 - a2)

max_cum_l = 0
cum_l = 0
L = [0]
for idx_l in range(0, N - 1, 2):
    cum_l += dA[idx_l]
    max_cum_l = max(max_cum_l, cum_l)
    L.append(max_cum_l)
max_cum_r = 0
cum_r = 0
R = [0]
for idx_r in range(N - 2, -1, -2):
    cum_r -= dA[idx_r]
    max_cum_r = max(max_cum_r, cum_r)
    R.append(max_cum_r)
R.reverse()
if N%2:
    ma = -(1<<60)
    for l, r in zip(L, R):
        if ma < l+r:
            ma = l+r
    print(ans + ma)
else:
    print(max(L) + ans)

Solution (Python):
import functools
import sys

sys.setrecursionlimit(1000000)

N, = (int(x) for x in input().split())
arr = [int(x) for x in input().split()]

@functools.lru_cache(None)
def dp(i, k):
    if k <= 0:
        return 0
    rem = N - i
    if k > (rem // 2) + (rem % 2):
        return -float('inf')
    return max(arr[i] + dp(i + 2, k - 1), dp(i + 1, k))


sol = dp(0, N // 2)

print(sol)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
k = n//2
d = dict()
d[(-2,0)] = 0
for i in range(n):
    nxt = dict()
    discard = []
    for (prev, cnt), score in d.items():
        if i-prev == 1:
            continue
        if cnt == k:
            continue
        nprev = i
        ncnt = cnt+1
        nscore = score+a[i]
        tmp = (nprev, ncnt)
        if tmp not in nxt or nxt[tmp] < nscore:
            nxt[tmp] = nscore
        r = n-1-i
        if cnt + (r+1)//2 < k:
            discard.append((prev, cnt))
    for key, value in nxt.items():
        d[key] = value
    for key in discard:
        d.pop(key)
ans = -float("inf")
for key, value in d.items():
    if key[1] == k:
        ans = max(ans, value)
print(ans)