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 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):
N = int(input())
A = [int(a) for a in input().split()]
if N % 2 == 0:
    x, y, px, py = 0, 0, 0, -1<<100
    for a in A:
        x, y, px, py = px+a, max(x, py+a), x, y
    print(max(x, y))
else:
    x, y, z, px, py, pz = 0, 0, 0, 0, -1<<100, -1<<100
    for a in A:
        x, y, z, px, py, pz = px+a, max(x, py+a), max(y, pz+a), x, y, z
    print(max(y, z))

Solution (Python):

import sys
from itertools import accumulate
sys.setrecursionlimit(10**8)
INF = float("inf")

import math


def array(*args, initial=0):
    pre = "["*len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range("+str(a)+")]"
    S = pre + str(initial) + post
    return eval(S)


def solve(N: int, A: "List[int]"):

    if N % 2 == 0:
        K = 2
    else:
        K = 3

    DP = array(N, K, initial=-10**9)
    DP[0][0] = A[0]
    DP[1][1] = A[1]
    if K == 3:
        DP[2][2] = A[2]
    for i in range(1, N):
        for k in range(K):
            if i == k and i < K:
                continue
            DP[i][k] = DP[i-2][k]
            if k-1 >= 0:
                DP[i][k] = max(DP[i][k], DP[i-3][k-1])
            if k-2 >= 0:
                DP[i][k] = max(DP[i][k], DP[i-4][k-2])
            DP[i][k] += A[i]
    if N % 2 == 0:
        print(max(DP[-1][1], DP[-2][0]))
    else:
        print(max(DP[-1][2], DP[-2][1], DP[-3][0]))
    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):
N = int(input())
A = list(map(int,input().split()))
odds_or_even = N%2+2
inf = -float("inf")
dp = [[inf for _ in range(N+1)] for _ in range(odds_or_even)]
dp[0][0] = 0
for i in range(N):
    dp[0][i+1] = dp[0][i]+A[i]*((i+1)%2)
for j in range(1,odds_or_even):
    for i in range(N):
        dp[j][i+1] = max(dp[j-1][i],dp[j][i]+A[i]*((i+j+1)%2))

print(dp[odds_or_even-1][N])

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]

sm_e = []
sm_o = []

e = 0
o = 0

for i in range(n):
    if i % 2 == 0:
        e += a[i]
        sm_e.append(e)
    else:
        o += a[i]
        sm_o.append(o)

tot_e = sm_e[-1]
tot_o = sm_o[-1]

m = len(sm_o)

if n % 2 == 0:
    ans = max(tot_e, tot_o)
    for i in range(m):
        ans = max(ans, sm_e[i] + tot_o - sm_o[i])
    
    
    print(ans)
    exit()

ans = tot_o

for i in range(m):
    ans = max(ans, sm_e[i]+tot_o-sm_o[i])


l = [0]*m
for i in range(m):
    l[i] = sm_e[i]-sm_o[i]

val = l[0]
tmp = 0

for i in range(m-1):
    ans = max(ans, sm_o[i] + tot_e - sm_e[i+1])
    if i != 0:
        if val < l[i]:
            val = l[i]
    ans = max(ans, sm_o[i] + tot_e - sm_e[i+1] + val)

for i in range(n):
    if i % 2 == 0:
        ans = max(ans, tot_e - a[i])

print(ans)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
inf=float("inf")
DP=[[-inf]*4 for _ in range(n+1)]
DP[0][2]=0
for i,a in enumerate(A):
  if (i+1)%2==0:
    DP[i+1][0]=DP[i][3]+a
    if i>=1:
      DP[i+1][0]=max(DP[i+1][0],DP[i-1][2]+a)
    DP[i+1][2]=DP[i][0]
    DP[i+1][3]=max(DP[i][1],DP[i][3])
    if i>=1:
      DP[i+1][3]=max(DP[i+1][3],DP[i-1][2])
  else:
    DP[i+1][0]=DP[i][2]+a
    DP[i+1][1]=DP[i][3]+a
    DP[i+1][3]=max(DP[i][0],DP[i][2])
if n%2==0:
  print(max(DP[n][0],DP[n][2]))
else:
  print(max(DP[n][1],DP[n][3]))

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

DP=[[-10**16 for i in range(N)]for j in range(3)]

DP[1][0]=0
DP[2][0]=0
DP[2][1]=0
DP[0][0]=A[0]
DP[1][1]=A[1]
if N>=3:
    DP[2][2]=A[2]

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

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
k = 1+N%2 
INF = 10**18

dp = [[-INF for _ in range(4)] for _ in range(202020)]
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)
print(dp[N][k])

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

Solution (Python):
from collections import defaultdict
INF = -1000000000000001

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

a = int(n/2)

dpa = defaultdict(lambda: -INF)


dpa[(0,0)] = 0
dpa[(1,0)] = 0
dpa[(1,1)] = l[0]
j = 1
for i in range(2,n+1):
	if i == j*2:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])

	else:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])

		if (i != n):
			j += 1


			dpa[(i,j)] = dpa[(i-2,j-1)]+l[i-1]


print(dpa[n,a])

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):
from math import inf


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

dp = [[-inf] * 3  for _ in range(n + 1)]
k = 1 + n % 2
dp[0][0] = 0
for i in range(n):
    for j in range(k + 1):
        if j < k:
            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)
print(dp[n][k])

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

inf = 10 ** 18

dp = [[-inf] * 3  for _ in range(n + 1)]
k = 1 + n % 2
dp[0][0] = 0
for i in range(n):
    for j in range(k + 1):
        if j < k:
            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)
print(dp[n][k])

Solution (Python):
import sys
sys.setrecursionlimit(2000000000)
N = int(input())
import math
l = [int(x) for x in input().split()]
tobi = [0]*(math.ceil(N/2))
tobi[0] = l[0]
for i in range(1,math.ceil(N/2)):
    tobi[i] = tobi[i-1] + l[i*2]
from functools import lru_cache
@lru_cache(maxsize=1000000000)
def motomeru(x,y):
    if y == 0 or x == 0 or x == 1:
        return 0
    elif x % 2 == 0:
        return max(motomeru(x-2,y-1)+l[x-1],tobi[math.floor((x-1)/2)])
    else:
        return max(motomeru(x-2,y-1)+l[x-1],motomeru(x-1,y))
print(motomeru(N,N//2))

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

N = int(input())
A = list(map(int, input().split()))
K = 1+N%2
dp = [[-10**18]*(K+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(K+1):
        if j+1<=K:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
        
        dp[i+1][j] = max(dp[i+1][j], dp[i][j]+(A[i] if (i+j)%2==0 else 0))

print(dp[N][K])

Solution (Python):
import sys
sys.setrecursionlimit(2000000000)
N = int(input())
import math
l = [int(x) for x in input().split()]
tobi = [0]*(math.ceil(N/2))
tobi[0] = l[0]
for i in range(1,math.ceil(N/2)):
    tobi[i] = tobi[i-1] + l[i*2]
from functools import lru_cache
@lru_cache(maxsize=1000000000)
def motomeru(x,y):
    if y == 0 or x == 0 or x == 1:
        return 0
    elif x % 2 == 0:
        return max(motomeru(x-2,y-1)+l[x-1],tobi[math.floor((x-1)/2)])
    else:
        return max(motomeru(x-2,y-1)+l[x-1],motomeru(x-1,y))
print(motomeru(N,N//2))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    m = N // 2
    dp = [defaultdict(lambda: -INF)] * 2
    dp[0][0] = 0
    for i, a in enumerate(A):
        ndp = [defaultdict(lambda: -INF)] * 2
        l = m - ((N-i) // 2)
        ndp[0] = dp[1]
        for k, v in dp[0].items():
            if k+1 >= l:
                ndp[1][k+1] = max(ndp[1][k+1], v+a)
            if k+2 >= l:
                ndp[0][k] = max(ndp[0][k], v)
        dp = ndp
    return max(dp[0][m], dp[1][m])


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = lr()
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0, 0] = 0
    for i in range(N):
        for j in range(max(i//2-1, 0), i//2+2):
            dp[i+1, j+1, 1] = dp[i, j, 0]+A[i]
            dp[i+1, j, 0] = max(dp[i, j, 0], dp[i, j, 1])
    
    print(max(dp[N, N//2, 1], dp[N, N//2, 0]))
resolve()

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
m=-10**15

dp1=[[m,m,m] for i in range(n)] 
dp0=[[m,m,m] for i in range(n)] 
dp1[0][0]=A[0]
dp0[0][1]=0 
for i in range(1,n):
    for j in range(3):
        dp1[i][j]=max(dp1[i][j],dp0[i-1][j]+A[i])
        dp0[i][j]=max(dp0[i][j],dp1[i-1][j])
        if j!=2:
            dp0[i][j+1]=max(dp0[i][j+1],dp0[i-1][j])
if n%2==0:
    print(max(dp1[n-1][1],dp0[n-1][0]))
else:
    print(max(dp1[n-1][2],dp0[n-1][1]))

Solution (Python):
from collections import defaultdict

INF = 2 ** 60
dp = defaultdict(lambda: -INF)

n = int(input())
a = list(map(int, input().split())) + [0] * 10

dp[(0, 0)] = 0
dp[(1, 1)] = a[0]

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

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

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

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

print(max(dp))

Solution (Python):
INF = float("inf")
n = int(input())
a = list(map(int, input().split())) + ([0]*5)
s = 2 + n % 2 
dp = [[-INF] * s for _ in range(n+5)]
for i in range(s): dp[i][i] = a[i]

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

print(max([dp[n-i][s-i] for i in range(1, s+1)]))

Solution (Python):
N_all=int(input())
A=list(map(int,input().split()))
f_inf=-float("inf")
odds_or_even=N_all%2+2
dp=[[f_inf for x in range(N_all+1)] for x in range(odds_or_even)]
dp[0][0]=0

for i in range(N_all):
  dp[0][i+1]=dp[0][i]+A[i]*((i+1)%2)
for j in range(1,odds_or_even):
  for i in range(N_all):
    dp[j][i+1]=max(dp[j][i]+A[i]*((i+j+1)%2),dp[j-1][i])
        
print(dp[odds_or_even-1][N_all])

Solution (Python):
def examA():
    N = SI()
    ans = "No"
    for s in N:
        if s=="7":
            ans = "Yes"
    print(ans)
    return

def examB():
    N = I()
    ans = 0
    for i in range(1,N+1):
        if i%3==0:
            continue
        if i%5==0:
            continue
        ans += i
    print(ans)
    return

def examC():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    K = I()
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            cur = gcd(i,j)
            for k in range(1,K+1):
                ans += gcd(cur,k)
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    R = [0]*(N+1)
    G = [0]*(N+1)
    B = [0]*(N+1)
    for i in range(N):
        s = S[i]
        R[i+1] += R[i]
        G[i+1] += G[i]
        B[i+1] += B[i]
        if s=="R":
            R[i+1] += 1
        elif s=="G":
            G[i+1] += 1
        elif s=="B":
            B[i+1] += 1
    ans = 0
    for l in range(N):
        Ls = S[l]
        for r in range(l+3,N):
            Rs = S[r]
            if (Ls=="R" and Rs=="B") or (Ls=="B" and Rs=="R"):
                ans += G[r] - G[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="G":
                        ans -= 1
            elif (Ls=="R" and Rs=="G") or (Ls=="G" and Rs=="R"):
                ans += B[r] - B[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="B":
                        ans -= 1
            elif (Ls=="G" and Rs=="B") or (Ls=="B" and Rs=="G"):
                ans += R[r] - R[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="R":
                        ans -= 1
    print(ans)
    return

def examE():
    N, K = LI()

    ans = 0
    print(ans)
    return

def examF():
    N = I()
    A = LI()

    if N%2==0:
        O = [0] * N
        E = [0] * N
        for i in range(N):
            O[i] += O[i - 1]
            E[i] += E[i - 1]
            if i % 2 == 0:
                O[i] += A[i]
            else:
                E[i] += A[i]
        
        ans = max(O[-1],E[-1])
        print(ans)
        return

    def dfs(n,k):
        if (n+2)//2 <k:
            return -inf
        if k == 0:
            return 0
        if n==0:
            if k==1:
                return A[0]
            return -inf
        if n==1:
            if k==1:
                return max(A[0],A[1])
            return -inf
        res = max(A[n]+dfs(n-2,k-1),dfs(n-1,k))
        return res

    ans = dfs(N-1,N//2)
    
    print(ans)
    return

def examF2():
    N = I()
    A = LI()

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

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF2()

"""
27
18 18 19 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49
"""

Solution (Python):
n = int(input())
ai = [int(i) for i in input().split()]

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

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

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

Solution (Python):

from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]



dp = defaultdict(lambda: -float("inf"))


dp[(0, 0, 0)] = 0


for i, a in enumerate(A, 1):
    
    for x in range((i // 2) - 1, (i + 1) // 2 + 1):
        dp[(i, x, 0)] = max(dp[(i - 1, x, 0)], dp[(i - 1, x, 1)])
        dp[(i, x, 1)] = dp[(i - 1, x - 1, 0)] + a

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

Solution (Python):

from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]



dp = defaultdict(lambda: -float("inf"))


dp[(0, 0, 0)] = 0

for i, a in enumerate(A, 1):
    for x in range((i // 2) - 1, (i + 1) // 2 + 1):
        dp[(i, x, 0)] = max(dp[(i - 1, x, 0)], dp[(i - 1, x, 1)])
        dp[(i, x, 1)] = dp[(i - 1, x - 1, 0)] + a

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

Solution (Python):


import collections
def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)

def main():
    pass
    N, *A = map(int, open(0).read().split())
    a = dict(enumerate(A, 1))
    dp = collections.defaultdict(lambda: -float("inf"))
    dp[0, 0] = 0 
    dp[1, 0] = 0 
    dp[1, 1] = a[1]
    for i in range(2, N + 1):
        jj = range(max(i // 2 - 1, 1), (i + 1) // 2 + 1)
        for j in jj:
            x = dp[i - 2, j - 1] + a[i]
            y = dp[i - 1, j]
            dp[i, j] = max(x, y)
    print(dp[N, N // 2])

if __name__ == "__main__":
    main()

Solution (Python):


import collections
import math
def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)

def main():
    pass
    N, *A = map(int, open(0).read().split())
    a = dict(enumerate(A, 1))
    dp = collections.defaultdict(lambda: -float("inf"))
    dp[0, 0] = 0 
    dp[1, 0] = 0 
    dp[1, 1] = a[1]
    for i in range(2, N + 1):
        jj = range(max(math.floor(i // 2 - 1), 1), math.ceil((i + 1) // 2) + 1)
        for j in jj:
            x = dp[i - 2, j - 1] + a[i]
            y = dp[i - 1, j]
            dp[i, j] = max(x, y)
    print(dp[N, N // 2])

if __name__ == "__main__":
    main()

Solution (Python):


import collections
import math
def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)

N, *A = map(int, open(0).read().split())
a = dict(enumerate(A, 1))

dp = collections.defaultdict(lambda: -float("inf"))
dp[0, 0] = 0 
dp[1, 0] = 0 
dp[1, 1] = a[1]
for i in range(2, N + 1):
    jj = range(max(math.floor(i // 2 - 1), 1), math.ceil((i + 1) // 2) + 1)
    debug(jj)
    for j in jj:
        x = dp[i - 2, j - 1] + a[i]
        y = dp[i - 1, j]

        dp[i, j] = max(x, y)
        debug([i - 2, j - 1])
        debug([i - 1, j])
        debug([i, j])
        debug(dp[i, j])
print(dp[N, N // 2])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)

def find(idx, c, arr, tb):

    if c == 0:
        return 0

    if idx <= 0 or idx < 2 * c - 1:
        return float('-inf')

    if (idx, c) in tb:
        return tb[(idx, c)]

    rs = find(idx - 2, c - 1, arr, tb) + arr[idx - 1]
    rs = max(rs, find(idx - 1, c, arr, tb))

    tb[(idx, c)] = rs
    return rs

def main():

    n = int(input())
    arr = [int(e) for e in input().split(' ')]
    print(find(n, n // 2, arr, {}))
    return 0


main()

Solution (Python):


inf = float('inf')

def main():
    
    N = int(input())
    A = [0] + list(map(int, input().split()))



    dp1 = [-inf] * (N+1)
    dp2 = [-inf] * (N+1)
    dp1[1] = 0
    dp2[1] = 0
    dp1[2] = A[1]
    dp2[2] = A[2]
    for i in range(3, N+1):
        if i%2 == 0:
            dp1[i] = dp1[i-2] + A[i-1]
            dp2[i] = max(dp2[i-2] + A[i], dp1[i-2] + A[i])
        else:
            dp1[i] = max(dp2[i-1], dp1[i-2]+A[i-1])
            dp2[i] = max(dp2[i-2] + A[i], dp1[i-2] + A[i])

    if N % 2 == 0:
        ans = max([dp1[N], dp2[N]])
    else:
        ans = max(dp1[-2:] + dp2[-2:])

    
    
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys








sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


inf = float('inf')


def main():
    
    N = int(readline())
    A = list(map(int, readline().split()))

    K = N//2
    DP0 = [-inf] * N
    DP1 = [-inf] * N
    DP2 = [-inf] * N

    DP2[0] = A[0]
    DP2[1] = max(A[0], A[1])
    DP1[:2] = [0] * 2
    DP0[:4] = [0] * 4
    for i in range(2, N):
        if i%2 == 0:
            DP2[i] = DP2[i-2] + A[i]
            DP1[i] = max(DP2[i-1], DP1[i-2] + A[i])
            DP0[i] = max(DP1[i-1], DP0[i-2] + A[i])
        else:
            DP2[i] = max(DP2[i-2] + A[i], DP2[i-1])
            DP1[i] = max(DP1[i-1], DP1[i-2] + A[i])
            DP0[i] = max(DP0[i-1], DP0[i-2] + A[i])

    if N%2 == 0:
        ans = DP2[N-1]
    else:
        ans = DP1[N-1]

    
    
    
    print(ans)


if __name__ == "__main__":
    main()

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














dp = [[0 for i in range(3)] for j in range(n)]
ans = 0

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

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

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

else:
	dp = [[-10**20 for _ in range(3)] for _ in range(n)]
	dp[0][0] = a[0]
	dp[0][1] = 0
	dp[1][1] = a[1]
	dp[0][2] = 0
	dp[1][2] = 0
	dp[2][2] = a[2]

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

print(max(dp[n-1]))

Solution (Python):
from collections import defaultdict

INF = float("inf")


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

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

for i, a in enumerate(A, 1):
    j = (i - 1) // 2
    for n in [j, j + 1]:
        I[(i, n)] = a + O[(i - 1, n - 1)]
        O[(i, n)] = max(O[(i - 1, n)], I[(i - 1, n)])

print(max(I[(N, N // 2)], O[(N, N // 2)]))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
K = 2 if N%2 else 1
INF = float('inf')
dp = [[[-INF]*2 for _ in range(K+1)] for _ in range(N+1)]
dp[0][K][0] = 0 
for i,a in enumerate(A):
    for k in range(K,-1,-1):
        dp[i+1][k][0] = max(dp[i+1][k][0], dp[i][k][1])
        dp[i+1][k][1] = max(dp[i+1][k][1], dp[i][k][0] + a)
        if k:
            dp[i+1][k-1][0] = max(dp[i+1][k-1][0], dp[i][k][0])
print(max(max(row) for row in dp[-1][:2]))

Solution (Python):
from collections import defaultdict

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

dp = defaultdict(lambda: -10**18)
dp[(0,0,False)] = 0

for i in range(n):
    for j in range(i//2-1,i//2+2):
        dp[(i+1,j,False)] = max(
            dp[(i,j,False)],
            dp[(i,j,True)]
        )
        dp[(i+1,j,True)] = dp[(i,j-1,False)] + al[i]

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

Solution (Python):
N = int(input())
num = list(map(int, input().split()))
dp_odd = [0, num[0]]
dp_even = max(num[0], num[1])
for i in range(2, N):
  if (i + 1) % 2 == 1:
    dp_odd = [max(dp_odd[0] + num[i], dp_even), dp_odd[1] + num[i]]
  else:
    dp_even = max(dp_even + num[i], dp_odd[1])

if N % 2 == 0:
  print(dp_even)
else:
  print(dp_odd[0])

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):
import sys, math
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))
    """
    dp[i][j] = (1からi番目の数のうちどの２個も連続しないようにj個選んだ時の和の最大)
    と置くらしい。何故その発想になるんだ？？
    最初は左右で分けて尺取りみたいなことをすれば行けると思ったが、左右の分け目を１つずらしたら
    最適解がガラッと変わって困った　→　じゃあDP、って感じなのかなあ

    このままだとO(N^2)なので状態数を減らす。
    １．j個は連続しないようにとるので、j <= (1 + i) // 2は確定。(iは1-indexedなことに注意)
    ２．残った(N - i)から連続しないように(N // 2 - j)個選ぶには、(N // 2 - j) <= (1 + N - i) // 2、
    　　すなわち(i - 3) // 2 <= jが必要。
    　　（j = 0,1,とか考えてもいいが、最終的にdp[N][N // 2]を求めるのにこれらは寄与しない）
    以上より、(i - 3) // 2 <= j <= (i + 1) // 2の範囲のみでdpすれば十分。

    肝心の遷移だが、A = [3, 1, 4, 1, 5, 9, 2]を例にとると
            i\j|  0  1  2   3   4       dp[5][1] = max(A[5], dp[4][1])
            ----------------------      dp[5][2] = max(A[5] + dp[3][1], dp[4][2])
              1|  0  3                  dp[5][3] = A[5] + dp[3][2]
              2|  0  3
              3|  0  4  7               dp[6][2] = max(A[6] + dp[4][1], dp[5][2])
              4|     4  7               dp[6][3] = max(A[6] + dp[4][2], dp[5][3])
              5|     5  9  12
              6|        9  12           のように、最後の数をとるか取らないかで場合分けすればよい。
              7|        9  12  14       ただしiが奇数の場合、dp[i][(i + 1) // 2]は必ずA[i]を
                                        加えざるを得ないため場合分けは起きないことに注意。
    """

    
    odd = [0, A[1], 0]
    even = [0, max(A[1], A[2])]
    for i in range(3, N + 1):
        if i % 2 == 0:
            even[0] = max(A[i] + even[0], odd[1])
            even[1] = max(A[i] + even[1], odd[2])
        elif i > 3:
            odd[0] = max(A[i] + odd[0], even[0])
            odd[1] = max(A[i] + odd[1], even[1])
            odd[2] = A[i] + odd[2]
        else:
            odd[1] = max(A[1:4])
            odd[2] = A[1] + A[3]
    if N % 2 == 0:
        print(even[1])
    else:
        print(odd[1])


if __name__ == "__main__":
    main()