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 = [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):
N = int(input())
S = list(map(int,input().split()))
import numpy as np
get_DP  = [[-np.inf for i in range(3)] for j in range(N)]
pass_DP = [[-np.inf for i in range(3)] for j in range(N)]
for i in range(N):
    
    get_DP[i][0] = (pass_DP[i-1][0] if i>0 else 0) + S[i] 
    pass_DP[i][0] = get_DP[i-1][0]
    if i>0:
        get_DP[i][1] = (pass_DP[i-1][1] if i!=1 else 0) + S[i]
        pass_DP[i][1] = max(pass_DP[i-1][0], get_DP[i-1][1])
    if i>1:
        get_DP[i][2] = (pass_DP[i-1][2] if i!=2 else 0) + S[i]
        pass_DP[i][2] = max(pass_DP[i-1][1], get_DP[i-1][2])

    
print(max(get_DP[-1]+pass_DP[-1][:1+N%2]))

Solution (Python):
from math import gcd
from functools import reduce
 
n=int(input())
ar=list(map(int,input().split(' ')))
 
dp=[[-(10**20)]*6 for i in range(n+5)]+[[0]+[-(10**20)]*8 for i in range(3)]
 
 

def cn(z,j):
	return (z-j+1)//2
ans=-(10**20)
for i in range(n):
	idx=int(i)
	dp[idx]=dp[idx-2].copy()
	for j in range(0,5):
			for k in range(j+1):
					dp[idx][j]=max(dp[idx][j],dp[idx-k-2][j-k])
	for j in range(5):
		dp[i][j]+=ar[i]
		if cn(i+1,j)==n//2:
			ans=max(ans,dp[i][j])
print(ans)

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):
N = int(input())
*A, = map(int,input().split())

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

Solution (Python):








import sys
sys.setrecursionlimit(10**9)

from functools import lru_cache

def main():
    N = int(input())
    INF = 10**18
    nums = list(map(int, input().split()))
    @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 < 2 * n - 1:
        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()))

dp_g = A[1]
dp_k = A[0]
dp = [0, max(dp_g, dp_k)]

for i in range(2, N):
    if i % 2 == 1:
        dp_g = max(dp_k, dp_g) + A[i]
        dp_k += A[i - 1]
        dp.append(max(dp_g, dp_k))
    elif i % 2 == 0:
        dp.append(max(dp[i - 1], dp[i - 2] + A[i]))

print(dp[N - 1])

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

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

def num_left(pos):
	if pos % 2 == 0:
		return (n - pos) // 2 + 1
	else:
		return (n - pos - 1) // 2 + 1

d = [{} for i in range(n)]
for i in range(n):

	if i < 2:
		d[i][0] = 0
		d[i][1] = a[i]

	else:			
		left = num_left(i + 2)
		
		j = i - 2
		while j >= 0:
			max_count = max(d[j].keys())
			
			if max_count + left + 1	 < n // 2: 
				break

			else: 
				for count, v in d[j].items():
					
					if count + left + 1 >= n // 2:
						if count + 1 in d[i]:
							d[i][count + 1] = max(d[i][count + 1], v + a[i])
						else:
							d[i][count + 1] = v + a[i]							
			j -= 1

		if 1 + left >= n // 2:
			d[i][0] = 0

best = None
for i in range(n):
	for count, result in d[i].items():
		if count == n // 2:
			if best is None:
				best = result
			else:
				best = max(best, result)


print(best)

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

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

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

else:
    dp = [[0, 0, 0] for i in range(N)]
    dp[0] = [A[0], 0, 0]

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

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

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

if  N % 2 == 0:
    M =  N // 2
    even_A = [A[i* 2] for i in range(M)]
    odd_A = [A[i* 2 + 1] for i in range(M)]
    even_sum = []
    _sum = 0
    for a in even_A:
        _sum += a
        even_sum.append(_sum)
    odd_sum = []
    _sum = 0
    for a in odd_A:
        _sum += a
        odd_sum.append(_sum)
    ans = max(odd_sum[-1], even_sum[-1])
    for i in range(M):
            x = even_sum[i] + odd_sum[-1] - odd_sum[i]
            ans = max(ans, x)
    print(ans)
    exit()
M =  N // 2

even_A = [A[i* 2] for i in range(M+1)]
odd_A = [A[i* 2 + 1] for i in range(M)]
even_sum = []
_sum = 0
for a in even_A:
    _sum += a
    even_sum.append(_sum)
odd_sum = []
_sum = 0
for a in odd_A:
    _sum += a
    odd_sum.append(_sum)

all_even = even_sum[-1] - min(even_A)
diff_odd_even = [odd_sum[k] - even_sum[k+1] for k in range(M)]
diff_max_odd_even = []
diff_max = diff_odd_even[-1]
for k in range(M):
    diff_max = max(diff_max, diff_odd_even[-k-1])
    diff_max_odd_even.append(diff_max)
diff_max_odd_even.reverse()

ans = all_even
for i in range(M):
        x = even_sum[i] + odd_sum[-1] - odd_sum[i]
        y = odd_sum[i] + even_sum[-1] - even_sum[i+1]
        z = even_sum[i] + - odd_sum[i] + even_sum[-1] + diff_max_odd_even[i]
        ans = max(ans, x, y, z)
print(ans)

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

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


main()

Solution (Python):
N = int(input())
A = tuple(map(int,input().split()))
from collections import defaultdict
dp_non = defaultdict(lambda: -2**60)
dp_take = defaultdict(lambda: -2**60)
dp_non[(0,0)] = 0
for i,x in enumerate(A,1):
    j = (i-1)//2
    for n in (j,j+1):
        dp_non[(i,n)] = max(dp_non[(i-1,n)],dp_take[(i-1,n)])
        dp_take[(i,n)] = dp_non[(i-1,n-1)]+x
print(max(dp_non[N,N//2],dp_take[(N,N//2)]))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 18
if n % 2:
    dp = [[[-INF,-INF,-INF] for i in range(2)] for i in range(n+1)]
    dp[0][0][0] = 0
    
    for i,v in enumerate(a):
        for j in range(2):
            if j:
                dp[i+1][0][0] = max(dp[i+1][0][0],dp[i][1][0])
                dp[i+1][0][1] = max(dp[i+1][0][1],dp[i][1][1])
                dp[i+1][0][2] = max(dp[i+1][0][2],dp[i][1][2])
            else:
                dp[i+1][1][0] = max(dp[i+1][1][0],dp[i][0][0] + v)
                dp[i+1][0][1] = max(dp[i+1][0][1],dp[i][0][0])
                dp[i+1][1][1] = max(dp[i+1][1][1],dp[i][0][1] + v)
                dp[i+1][0][2] = max(dp[i+1][0][2],dp[i][0][1])
                dp[i+1][1][2] = max(dp[i+1][1][2],dp[i][0][2] + v)
    print(max(max(dp[n][0]),max(dp[n][1])))
else:
    odd_sum,even_sum = 0,0
    cumsum = []
    for k,v in enumerate(a):
        if k % 2:
            odd_sum += v
            cumsum.append(odd_sum)
        else:
            even_sum += v
            cumsum.append(even_sum)
    ans = max(cumsum[n-2],cumsum[n-1])
    for i in range(2,n,2):
        ans = max(ans, cumsum[i-2]+cumsum[n-1]-cumsum[i-1])
    print(ans)

Solution (Python):
N = int(input())
MINF = float('-inf')
As = (map(int, input().split()))

dp = [[[0 for ___ in range(2)] for __ in range(2)] for _ in range(N+3)]

if N % 2 == 0:
    for i, a in enumerate(As):
        if i % 2 == 0:
            dp[i][0][0] = max(dp[i-2][1][1], dp[i-1][1][1])
            dp[i][0][1] = MINF
            dp[i][1][0] = MINF
            dp[i][1][1] = dp[i-2][1][1] + a
        else:
            dp[i][0][0] = MINF
            dp[i][0][1] = MINF
            dp[i][1][0] = dp[i-1][1][1]
            dp[i][1][1] = max(dp[i-3][1][1], dp[i-2][1][1]) + a
else:
    for i, a in enumerate(As):
        if i % 2 == 0:
            dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][1][1])
            dp[i][0][1] = dp[i-1][0][0] + a
            dp[i][1][0] = MINF
            dp[i][1][1] = dp[i-1][1][0] + a
        else:
            dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1])
            dp[i][0][1] = MINF
            dp[i][1][0] = dp[i-1][1][1]
            dp[i][1][1] = dp[i-1][0][0] + a
print(max(dp[N-1][0][0], dp[N-1][0][1], dp[N-1][1][0], dp[N-1][1][1]))

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

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

if N % 2 == 0: 
    B = [0] * (N // 2 + 1)
    W = [0] * (N // 2 + 1)
    for i in range(N // 2):
        B[i + 1] = B[i] + A[2 * i]
    for i in range(N // 2 - 1, -1, -1):
        W[i] = W[i + 1] + A[2 * i + 1]

    
    

    ans = -10 ** 16
    for i in range(N // 2 + 1):
        ans = max(ans, B[i] + W[i])

    print (ans)
    exit()

DP0 = [[-10 ** 16] * 2 for _ in range(N + 1)]
DP1 = [[-10 ** 16] * 2 for _ in range(N + 1)]
DP2 = [[-10 ** 16] * 2 for _ in range(N + 1)]

DP0[N][0] = 0 

for i in range(N - 1, -1, -1):
    a = A[i]
    
    DP0[i][0] = DP0[i + 1][1]
    DP0[i][1] = DP0[i + 1][0] + a

    DP1[i][0] = max(DP1[i + 1][1], DP0[i + 1][0])
    DP1[i][1] = DP1[i + 1][0] + a

    DP2[i][0] = max(DP2[i + 1][1], DP1[i + 1][0])
    DP2[i][1] = DP2[i + 1][0] + a
    
if N % 2 == 1:
    print (max(DP1[0][0], DP2[0][1]))
else:
    print (max(DP0[0][0], DP1[0][1]))

Solution (Python):

if __name__ == "__main__":
    n = int(input())
    nums = [int(s) for s in input().split()]
    odds = [0]        
    for num in nums[::2]:
        odds.append(num + odds[-1])
    
    res = [0]
    for i, num in enumerate(nums[1::2]):
        res.append(max(res[-1]+num, odds[i+1]))
    
    if n % 2 == 0:
        print(res[-1])
    else:
        ans = float('-inf')
        for i, r in enumerate(res):
            ans = max(ans, res[i] + odds[-1] - odds[i+1])
        print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = 1000000007

def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a<b:
        return a
    else:
        return b

def main():
    N = int(readline())
    A = list(map(int,readline().split()))
    if N%2==0:
        A.append(0)
        DP = [[[-10**27]*2 for j in range(2)] for i in range(N+2)]
        DP[0][0][0] = 0
        for i in range(N+1):
            DP[i+1][0][0] = DP[i][0][1]
            DP[i+1][1][0] = smax(DP[i][0][0],DP[i][1][1])
            DP[i+1][0][1] = DP[i][0][0]+A[i]
            DP[i+1][1][1] = DP[i][1][0]+A[i]
            
        print(DP[N+1][1][0])

    else:
        A.append(0)
        DP = [[[-10**27]*2 for j in range(3)] for i in range(N+2)]
        DP[0][0][0] = 0
        for i in range(N+1):
            DP[i+1][0][0] = DP[i][0][1]
            DP[i+1][1][0] = smax(DP[i][0][0],DP[i][1][1])
            DP[i+1][2][0] = smax(DP[i][1][0],DP[i][2][1])
            DP[i+1][0][1] = DP[i][0][0]+A[i]
            DP[i+1][1][1] = DP[i][1][0]+A[i]
            DP[i+1][2][1] = DP[i][2][0]+A[i]
            
        print(DP[N+1][2][0])

if __name__ == '__main__':
    main()

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

if __name__ == "__main__":
    main()

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

if n % 2 == 0:
    prefix = [0] * n
    suffix = [0] * n
    for i in range(0, n):
        prefix[i] += nums[i]
        if i - 2 >= 0:
            prefix[i] += prefix[i - 2]

    for i in range(n-1, -1, -1):
        suffix[i] += nums[i]
        if i + 2 < n:
            suffix[i] += suffix[i + 2]
    ans = max(prefix[-1], prefix[-2])

    for i in range(n):
        if i % 2 == 0 and  i + 2 < n:
            ans = max(ans, prefix[i] + suffix[i + 2])
        if i % 2 == 0 and  i + 3 < n:
            ans = max(ans, prefix[i] + suffix[i + 3])
        if i % 2 == 1 and i + 2 < n:
            ans = max(ans, prefix[i] + suffix[i + 2])
    print(ans)
else:
    dp = [[0] * n for i in range(3)] 
    
    dp[2][0] = nums[0]
    dp[0][1] = 0
    dp[1][1] = max(nums[0], nums[1])
    dp[2][1] = 0
    dp[0][2] = 0
    dp[1][2] = max(nums[:3])
    dp[2][2] = nums[0] + nums[2]
    if n == 3:
        print(max(nums))
        exit()
    dp[0][3] = max(nums[:4]) 
    dp[1][3] = max(nums[0] + nums[3], nums[0] + nums[2], nums[1] + nums[3])
    dp[2][3] = 0
    dp[0][4] = max(nums[:5])
    dp[1][4] = max([nums[i] + nums[j] for i in range(5) for j in range(i+2, 5)])
    dp[2][4] = nums[0] + nums[2] + nums[4]

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

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
INF = 10**16

ans = -INF

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

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if n<=3:print(max(a));exit()
if n&1:
  dp=[3*[-(10**20)]for _ in range(n)]
  dp[0][0]=a[0]
  for i in range(1,n):
    if i%2==0:
      dp[i][0]=dp[i-2][0]+a[i]
      if i>=3:dp[i][2]=max(dp[i-2][2]+a[i],dp[i-3][1]+a[i])
      else:dp[i][2]=a[i]
    else:
      if i>=3:dp[i][1]=max(dp[i-2][1]+a[i],dp[i-3][0]+a[i])
      else:dp[i][1]=a[i]
  print(max(dp[-1][2],dp[-2][1],dp[-3][0]))
else:
  b=[a[0]]
  c=[a[1]]
  for i in range(2,n):
    if i%2==0:b.append(b[-1]+a[i])
    else:c.append(c[-1]+a[i])
  ans=max(b[-1],c[-1])
  for i in range(n//2-1):
    ans=max(ans,b[i]+c[-1]-c[i])
  print(ans)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = 0, 0, 0, 0, 0, 0
    for i, a in enumerate(A):
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a if i >= 1 else a1,
                a2 + a if i >= 2 else a2)

    if N & 1:
        return max(b2, a1)
    else:
        return max(b1, a0)


print(main())

Solution (Python):
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

dp = [0]*n
b = a[0]

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

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

print(dp[-1])

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

m = 2+n%2
dp = [[-10**18]*m for i in range(n+2)]
dp[0][0] = 0
for i in range(n):
    for j in range(m):
        if i%2 == j%2:
            x = a[i]
        else:
            x = 0
        if dp[i+1][j] < dp[i][j] + x:
            dp[i+1][j] = dp[i][j] + x
        if j+1 < m and dp[i+1][j+1] < dp[i][j]:
            dp[i+1][j+1] = dp[i][j]
print(max(dp[n][m-2], dp[n][m-1]))

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

dp = [0]*N

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

    if i%2==1: 
        dp[i] = max(dp[i-2]+A[i],cum)

ans = dp[-1]


print(ans)

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

Solution (Python):
from math import gcd


def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))

n = inp()
nums = [0] + inlt()
dp = [0 for i in range(n + 1)]
s = [0 for i in range(n + 1)]
s[1] = nums[1]
for i in range(3,n,2):
    s[i] = s[i - 2] + nums[i]
if n == 1:
    print(nums[0])
elif n == 2:
    print(max(nums[1],nums[2]))
elif n == 3:
    print(max(nums[3],nums[1],nums[2]))
elif n == 4:
    print(max(nums[1] + nums[3],nums[1] + nums[4],nums[2] + nums[4]))
else:
    dp[1] = nums[1]
    dp[2] = max(nums[1],nums[2])
    dp[3] = max(nums[3],nums[1],nums[2])
    dp[4] = max(nums[1] + nums[3],nums[1] + nums[4],nums[2] + nums[4])
    for i in range(5,n + 1):
        if i % 2 == 0:
            dp[i] = max(dp[i - 2] + nums[i], s[i - 1]) 
        else:
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    print(dp[n])

Solution (Python):


N=int(input())

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

if N==2:
    print(max(0,A[0],A[1]))
    exit()
if N==3:
    print(max(0,A[0],A[1],A[2]))
    exit()

dp=[[-10**18 for i in range(N)] for j in range(3)]
dp[0][0]=A[0]
dp[1][1]=A[1]
dp[2][2]=A[2]

for n in range(3):
    for index in range(N):
        if dp[n][index]!=-1:
            if n!=2 and index+3<N:
                dp[n+1][index+3]=max(dp[n+1][index+3],dp[n][index]+A[index+3])
            if n==0 and index+4<N:
                dp[n+2][index+4]=max(dp[n+2][index+4],dp[n][index]+A[index+4])
            if index+2<N:
                dp[n][index+2]=max(dp[n][index+2],dp[n][index]+A[index+2])

a=(dp[0][-1])
b=(dp[1][-1])
c=(dp[2][-1])

print(max(a,b,c))

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


ruiseki0 = [0] * (n + 10) 
for i in range(n):
    ruiseki0[i + 1] = ruiseki0[i]
    if i % 2 == 0:
        ruiseki0[i + 1] += a[i]
        
l = [0] * (n + 1)
for i in range(n + 1):
    l[i] = ruiseki0[i]
    if i % 2 == 0:
        if i == 0:
            l[i] = 0
        else:
            l[i] = max(l[i - 2] + a[i - 1], l[i])


a = a[::-1]
ruiseki0 = [0] * (n + 10) 
for i in range(n):
    ruiseki0[i + 1] = ruiseki0[i]
    if i % 2 == 0:
        ruiseki0[i + 1] += a[i]

r = [0] * (n + 1)
for i in range(n + 1):
    r[i] = ruiseki0[i]
    if i % 2 == 0:
        if i == 0:
            r[i] = 0
        else:
            r[i] = max(r[i - 2] + a[i - 1], r[i])
   
ans = - 10 ** 20
for i in range(n):
    if n - i - 2 < 0:
        break
    if n % 2 == 0 and i % 2 == 0:
        continue
    ans = max(ans, l[i] + r[n - i - 2])
    
if n % 2 == 0:
    ans1 = 0
    ans2 = 0
    for i in range(n):
        if i % 2 == 0:
            ans1 += a[i]
        else:
            ans2 += a[i]
    ans = max(ans1, ans2, ans)
if n % 2 == 1:
    ans = max(ans, sum(a)- ruiseki0[n])
print(ans)

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

if n // 2 == 1:
    print(max(a))
    exit()
if n < 20:
    d = a.copy()
    
    for i in range(1, n // 2):
        b = [0] * n
        c = -10 ** 24
        ans = -10 ** 24
        for j in range(i * 2, n):
            c = max(c, a[j - 2])
            b[j] = c + d[j]
            ans = max(ans, c + d[j])

        a = b.copy()
    print(ans)
    exit()

b = a[:10]
e = [True]*10

for i in range(1, n // 2):
    c = [0] * 10
    f = [False]*10
    d = -10**24
    for j in range(10):
        if 2 * i + j >= n:
            continue
        if not e[j]:
            continue
        d = max(d, b[j])
        c[j] = d + a[2 * i + j]
        f[j] = True
    e = f.copy()
    b = c.copy()
ans = -10 ** 24
for i in range(10):
    if e[i]:
        ans = max(ans, b[i])
print(ans)

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

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
c = 0
if N%2 == 0:
    dp = [[0,0] for _ 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+2]
        dp[i+1][1] = max(dp[i][0] + A[2*i+3], dp[i][1] + A[2*i+3])
    
    print(max(dp[N//2-1][0],dp[N//2-1][1]))
else:
    dp = [[0,0,0] for _ 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+2]
        dp[i+1][1] = max(dp[i][0] + A[2*i+3], dp[i][1] + A[2*i+3])
        dp[i+1][2] = max(dp[i][0] + A[2*i+4], dp[i][1] + A[2*i+4], dp[i][2] + A[2*i+4])
    
    print(max(dp[N//2-1][0],dp[N//2-1][1],dp[N//2-1][2]))

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N = I()
A = LI()


if N%2 == 0:
    d = defaultdict(lambda:defaultdict(lambda:-float('inf')))
    d[0][1] = A[0]
    d[1][1] = max(A[0],A[1])
    for i in range(2,N):
        if i%2 == 0:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
        else:
            for j in [(i+1)//2]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
    print(d[N-1][N//2])
else:
    d = defaultdict(lambda:defaultdict(lambda:-float('inf')))
    d[0][1] = A[0]
    d[1][1] = max(A[0],A[1])
    for i in range(2,N):
        if i%2 == 0:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
        else:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
    a1 = d[N-1][N//2]
    n = 0
    for i in range(2,N,2):
        n += A[i]
    print(max(n,a1))

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

dp=[[0]*(N+1) for i in range(3)]

dp[0][1]=-float("inf")
dp[2][1]=A[1]
dp[0][2]=0
dp[1][2]=max(A[1],A[2])
dp[2][2]=-float("inf")

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

print(dp[1][N])

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

if N % 2 == 0:
  inf = float("inf")
  DP = [[-inf for i in range(2)] for i in range(N)]
  
  DP[0][0] = A[0]
  DP[1][1] = A[1]
  for i in range(2, N):
    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 - 2][0], DP[N - 1][1]))
  
else:
  
  inf = float("inf")
  DP = [[-inf for i in range(3)] for i 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] = 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]) + A[i]
  print(max(DP[N - 2][1], DP[N - 1][2]))