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
input = sys.stdin.buffer.readline


from collections import defaultdict

con = 10 ** 9 + 7

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

INF = float("inf")


def main():
	N = int(input())
	A = getlist()
	A += [-INF] * 10
	if N % 2 == 0:
		DP0 = [-INF] * (N + 10)
		DP1 = [-INF] * (N + 10)
		DP0[0] = A[0]
		DP1[1] = A[1]
		for i in range(N):
			DP0[i + 2] = max(DP0[i] + A[i + 2] , DP0[i + 2])
			DP1[i + 3] = max(DP0[i] + A[i + 3] , DP1[i + 3])

			DP1[i + 2] = max(DP1[i] + A[i + 2] , DP1[i + 2])

		ans = max(DP0[N - 2], DP1[N - 1])

		print(ans)


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

			DP1[i + 2] = max(DP1[i] + A[i + 2] , DP1[i + 2])
			DP2[i + 3] = max(DP1[i] + A[i + 3] , DP2[i + 3])
			
			DP2[i + 2] = max(DP2[i] + A[i + 2] , DP2[i + 2])

		ans = max(DP0[N - 3], DP1[N - 2], DP2[N - 1])

		print(ans)



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 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

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

Solution (Python):
n=int(input())
a = list(map(int,input().split()))
a0 = [0] * (n//2+1)
a1 = [0] * (n//2+1)
for i in range(n//2):
    a0[i+1] = a0[i] + a[i*2]
if n% 2 != 0:
    a0.append(a0[-1] + a[-1])

max_even = [0] * (n//2+1)
for i in range(n//2):
    max_even[i+1] = max(max_even[i]+a[2*i+1], a0[i+1])

ans = -1e9*n
if n%2 == 0:
    ans = max_even[-1]
else:
    for i in range(0,n//2+1):
        ans = max(ans, max_even[i] + a0[-1] - a0[i+1])
print(ans)

Solution (Python):


INF = -(10 ** 17)


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


def main():
    if N % 2 == 0:
        dp = [[INF] * 2 for _ 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]
            if i > 2:
                dp[i][1] = max(dp[i - 2][1] + A[i], dp[i - 3][0] + A[i])
        
        ans = max(dp[-1][1], dp[-2][0])
        print(ans)
    else:
        dp = [[INF] * 3 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]
        for i in range(3, N):
            dp[i][0] = dp[i - 2][0] + A[i]
            dp[i][1] = max(dp[i - 2][1] + A[i], dp[i - 3][0] + A[i])
            if i > 3:
                a = dp[i - 2][2] + A[i]
                b = dp[i - 3][1] + A[i]
                c = dp[i - 4][0] + A[i]
                dp[i][2] = max(a, b, c)
        
        ans = max(dp[-1][2], dp[-2][1], dp[-3][0])
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    A = read_list()
    dp = [[-10 ** 20 for _ in range(2)] for _ in range(N // 2 + 5)] 

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

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


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n=int(input())
    A=list(map(int,input().split()))
    if n==3 or n==2:
        return max(A)
    DP=[[None]*3 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):
        a=A[i]
        if i%2==0:
            DP[i][0]=DP[i-2][0]+a
            DP[i][2]=max(DP[i-2][2]+a,DP[i-3][1]+a,DP[i-4][0]+a)
        if i%2!=0:
            DP[i][1]=max(DP[i-2][1]+a,DP[i-3][0]+a)
    if n%2==1:
        ans=max(DP[-1][2],DP[-2][1],DP[-3][0])
        return ans
    ans=max(DP[-1][1],DP[-2][0])
    return ans
    
if __name__=='__main__':
    print(main())

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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
ans = 0
if n % 2 == 0:
  b = []
  for i in range(n//2):
    ans += a[2*i]
    b.append(a[2*i+1] - a[2*i])
  
  for i in range(1,n//2)[::-1]:
    b[i-1] += b[i]
  
  b.append(0)
  print(ans + max(b))
else:
  b = []
  c = []
  for i in range(n//2):
    ans += a[2*i]
    b.append(a[2*i+1] - a[2*i])
    c.append(a[2*i+2] - a[2*i+1])
  for i in range(1,n//2)[::-1]:
    b[i-1] += b[i]
    c[i-1] += c[i]
  
  
  d = c[:]
  d[-1] = max(d[-1],0)
  for i in range(1,n//2)[::-1]:
    d[i-1] = max(d[i-1],d[i],0)
  
  e = []
  for i in range(n//2):
    e.append(b[i]+d[i])
  
  e.append(0)
  print(ans + max(e))

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

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

S = [0]*N
S[0] = A[0]
S[1] = A[1]

for i in range(2,N):
    S[i] = S[i-2] + A[i]

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

else:
    M = A[0]
    for i in range(1,N//2+1):
        M = min(M,A[2*i])

    mss = - M
    s = - A[0]
    for i in range(N//2):
        s += A[2*i+1] - A[2*i+2]
        if s < 0:
            s = - A[2*i+2]
        elif mss < s:
            mss = s
        
    
    mss2 = - M
    t = - A[-1]
    for i in range(1,N//2+1):
        t += A[-2*i] - A[-2*i-1]
        if t < 0:
            t = - A[-2*i-1]
        elif mss2 < t:
            mss2 = t
    
    p = S[-2]
    for i in range(1,N):
        if i % 2 == 1:
            p = max(p,S[i]+S[-1]-S[i+1])
    
    print(max(S[-1]+mss,S[-1]+mss2,p))

Solution (Python):
n = int(input())
a = [int(c) for c in input().split()]
m = 0
t0 = [-1]*n 
t1 = [-1]*n 
t2 = [-1]*n 
t0[-1] = a[-1]
t1[-1] = 0
t2[-1] = a[-1]
tmp = 0
for i in range(-1, -n-1, -2):
    tmp += a[i]
    t2[i] = tmp
tmp = 0
for i in range(-2, -n-1, -2):
    tmp += a[i]
    t2[i] = tmp

    
for i in range(-2, -n-1, -1):
    if i%2==0:
        m= a[i]+t1[i+1]
        m = max(m, t2[i+1])
        t0[i] = m
        t1[i] = t0[i+1]

    else:
        m= a[i]+t1[i+1]
        m = max(m, t0[i+1])
        t0[i] = m
        t1[i] = t0[i+1]

        
print(t0[0])

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

if N%2==0:
    S = [0]*N
    s = 0
    for i in range(0, N, 2):
        s += A[i]
        S[i] = s

    ans = s = sum(A[1:N:2])
    for t in range(1, N, 2):
        s -= A[t]
        ans = max(ans, S[t-1]+s)
    print(ans)

else:
    S = [0]*N
    s = 0
    p = 0
    for t in range(2, N, 2):
        p += A[t-2]
        S[t] = max(S[t-2]+A[t-1], p)
    
    ans = s = sum(A[2:N:2])
    for t in range(2, N, 2):
        s -= A[t]
        ans = max(ans, S[t]+s)
    print(ans)

Solution (Python):
from itertools import accumulate,chain
from itertools import combinations

from random import randrange


def solve(A):
    N = len(A)
    oddacc = tuple(chain((0,),accumulate(A[1::2])))
    evenacc = tuple(chain((0,),accumulate(A[::2])))
    if N%2==0:
        return max(evenacc[i]+oddacc[-1]-oddacc[i] for i in range(N//2+1))

    
    res = max(evenacc[-1]-A[i*2] for i in range(N//2+1))
    
    def it():
        m = 0

        for i in reversed(range(N//2)):
            m = max(m+A[i*2+1], A[i*2+1]+evenacc[-1]-evenacc[i+2])
            yield m+evenacc[i]
    res = max(max(it()), res)
    return res

def naive(A):
    def it():
        for indices in combinations(range(len(A)), r=len(A)//2):
            if all(i+1!=j for i,j in zip(indices,indices[1:])):
                yield (sum(A[i] for i in indices), indices)

    return max(it())

if __name__ == '__main__':
    N = map(int,input().split())
    A = tuple(map(int,input().split()))
    print(solve(A))

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

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


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

Solution (Python):

N = int(input())

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

if N % 2 == 0:

    e = 0
    o = 0
    

    for i in range(N):

        if i % 2 == 0:
            e += A[i]
        else:
            o += A[i]

    el = [0]
    ol = [0]

    for i in range(N):

        if i % 2 == 0:
            el.append(el[-1] + A[i])
        else:
            ol.append(ol[-1] + A[i])

    eri = [0]
    ori = [0]

    for i in range(N-1,-1,-1):

        if i % 2 == 0:
            eri.append(eri[-1] + A[i])
        else:
            ori.append(ori[-1] + A[i])

    ans = max(e,o)


    for i in range(N//2+1):
        ans = max(ans,el[i]+ori[N//2-i])
    print (ans)

else:

    el = [0]
    ol = [0]

    for i in range(N):

        if i % 2 == 0:
            el.append(el[-1] + A[i])
        else:
            ol.append(ol[-1] + A[i])

    eri = [0]
    ori = [0]

    for i in range(N-1,-1,-1):

        if i % 2 == 0:
            eri.append(eri[-1] + A[i])
        else:
            ori.append(ori[-1] + A[i])

    ans = float("-inf")



    LS = [0]
    LSM = [0]
    for i in range(0,N-1,2):

        LS.append(LS[-1] + A[i] - A[i+1])
        LSM.append(max(LSM[-1],LS[-1]))

    RS = [0]
    RSM = [0]
    for i in range(N-1,0,-2):

        RS.append(RS[-1] + A[i] - A[i-1])
        RSM.append(max(RSM[-1],RS[-1]))

    EOE = float("-inf")
    for i in range(N//2+1):
        EOE = max(EOE , LSM[i] + RSM[N//2-i])

    
    for i in range(N):

        if i <= N//2:

            ans = max(ans , el[i]+ori[N//2-i] , ol[i]+eri[N//2-i] , el[i]+eri[N//2-i] , ol[-1] + EOE)

    print (ans)

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

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

ans = -float("inf")
if n % 2 == 0:
    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]
    print(max(D[-1]))

else:

    

    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]


    S = [0] * n
    S[0] = A[0]
    S[1] = A[1]
    for i in range(2, n):
        S[i] = A[i] + S[i-2]

    
    

    for i in range(0, n, 2):
        le = max(D[i//2-1]) if i>0 else 0
        ri = S[-1] - S[i]
        
        ans = max(ans, le+ri)

    A = A[::-1]

    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]
    

    S = [0] * n
    S[0] = A[0]
    S[1] = A[1]
    for i in range(2, n):
        S[i] = A[i] + S[i-2]
    

    for i in range(0, n, 2):
        le = max(D[i//2-1]) if i>0 else 0
        ri = S[-1] - S[i]
        
        ans = max(ans, le+ri)

    print(ans)

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

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

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

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


if N % 2 == 0 :
  extra = 2
else :
  extra = 3
  
N += 1
A = A + [-float('inf')]
  
dp = [[[-float('inf')] * extra for _ in range(2)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N) :
  a = A[i]
  for j in range(2) :
    for k in range(extra) :
      
      if j == 0 :
        dp[i+1][1][k] = max(dp[i+1][1][k], dp[i][j][k] + a)
      
      if j == 1 :
        dp[i+1][0][k] = max(dp[i+1][0][k], dp[i][j][k])
      if j == 0 and k != extra - 1 :
        dp[i+1][0][k + 1] = max(dp[i+1][0][k + 1], dp[i][j][k])


  

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

Solution (Python):

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

answer = [max(A[0],A[1])]

list_sum = A[::2]
for i in range(1,len(list_sum)):
  list_sum[i] += list_sum[i-1]

for i in range(2,N):
  if i==2:
    answer.append(max(A[0],A[1],A[2]))
  elif i%2==0:
    answer.append(max(answer[-1], answer[-2]+A[i]))
  else:
    answer.append(max(answer[-2]+A[i], list_sum[(i-1)//2]))

print(answer[-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):

import sys


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

    print(max(dp[N]))
    return


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

if __name__ == '__main__':
    main()

Solution (Python):
def solve(n, a_list):
    if n % 2 == 0:
        res_a = [0] * (n // 2 + 1)
        res_b = [0] * (n // 2 + 1)
        for i in range(0, n // 2):
            res_a[i + 1] = res_a[i] + a_list[i * 2]
        for i in range(n // 2 - 1, -1, -1):
            res_b[i] = res_b[i + 1] + a_list[i * 2 + 1]
        return max([res_a[i] + res_b[i] for i in range(n // 2 + 1)])
    else:
        
        dp = [[0] * 3 for _ in range(n)]
        dp[0][0] = a_list[0]
        dp[1][1] = a_list[1]
        dp[2][2] = a_list[2]
        for i in range(n):
            if i % 2 == 0:
                if i >= 2:
                    dp[i][0] = dp[i - 2][0] + a_list[i]
                    dp[i][1] = dp[i - 1][1]
                if i >= 3:
                    dp[i][2] = max(dp[i - 3][1] + a_list[i], dp[i - 2][2] + a_list[i])
            else:
                if i >= 3:
                    dp[i][1] = max(dp[i - 2][1] + a_list[i], dp[i - 3][0] + a_list[i])
                dp[i][0] = dp[i - 1][0]
                dp[i][2] = dp[i - 1][2]
        res_a = max(dp[-1])
        

        
        even = [a_list[i] for i in range(0, n, 2)]
        res_b = sum(even) - min(even)

        return max(res_a, res_b)


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(6, [1, 2, 3, 4, 5, 6]) == 12
    assert solve(5, [-1000, -100, -10, 0, 10]) == 0
    assert solve(10, [1000000000] * 10) == 5000000000


if __name__ == "__main__":
    test()
    main()

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n = n_in()

A = l_in()

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




if n%2 == 0:
    res = sum(A[::2])
    dp = [[0,0] 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):
        dp[i][0] = dp[i-2][0] + A[i]
        dp[i][1] = max(dp[i-3][0] + A[i], dp[i-2][1] + A[i])

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

res = sum(A[::2])-A[-1]
dp = [[0,0] 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-1):
    dp[i][0] = dp[i-2][0] + A[i]
    dp[i][1] = max(dp[i-3][0] + A[i], dp[i-2][1] + A[i])


res = max(res, dp[n-2][1])

dp = [[0,0,0] 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]
dp[3][1] = max(A[0],A[1])+A[3]

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


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

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

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

DP = [[- 10 ** 10] * 3 for _ in range(N)]

DP[0][0] = A[0]
DP[1][0] = A[1]
DP[2][0] = A[0] + A[2]
DP[2][1] = A[2]

for i in range(3, N):
  DP[i][0] = DP[i - 2][0] + A[i]
  DP[i][1] = DP[i - 2][1] + A[i]
  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])

ans = 0

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

print(ans)

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)

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):
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):
import numpy as np

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


A = np.array([0, 0] + A)

cum_0 = A[::2].cumsum()
cum_1 = A[1::2].cumsum()


ans = -float("inf")

if N % 2:
    cum_10 = cum_1.copy()
    cum_10 -= cum_0[1:]
    cum_01 = cum_0[:-1].copy()
    cum_01 -= cum_1

    cum_max_01 = np.zeros_like(cum_01)
    for i in range(1, len(cum_max_01)):
        cum_max_01[i] = max(cum_max_01[i - 1], cum_01[i])

    ans = (cum_max_01 + cum_10).max()
    ans += cum_0[-1]
else:
    for i in range(0, N // 2 + 1):
        tmp = cum_0[i] + (cum_1[-1] - cum_1[i])
        ans = max(ans, tmp)
print(ans)

pass

Solution (Python):
mod = 1000000007
eps = 10**-9
inf = 10**20


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    if N == 2 or N == 3:
        print(max(A))
        exit()

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


if __name__ == '__main__':
    main()

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

if n % 2 == 0:
    b = [0] * n
    for i in range(n):
        if i // 2 == 0:
            b[i] = a[i]
        else:
            if i % 2 == 0:
                b[i] = b[i - 2] + a[i]
            else:
                b[i] = max(b[i - 3], b[i - 2]) + a[i]
    print(max(b[-1], b[-2]))
else:
    b = []
    for i in range(2):
        temp = [0] * n
        b.append(temp)
    for i in range(n):
        if i // 2 == 0:
            b[0][i] = a[i]
        else:
            if i % 2 == 1:
                b[0][i] = max(b[0][i - 3], b[0][i - 2]) + a[i]
            else:
                b[0][i] = b[0][i - 2] + a[i]
                if i == 2:
                    b[1][i] = b[1][i - 2] + a[i]
                else:
                    b[1][i] = max(b[0][i - 4], b[0][i - 3], b[1][i - 2]) + a[i]
    print(max(b[1][-1], b[0][-2], b[0][-3]))

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007



def main():
	n = int(input())
	al = list(IN())
	if n == 2 or n == 3:
		return max(al)
	
	if n % 2 == 0:
		cc = [[0]*n,[0]*n]
		cc[0][0]=al[0]
		cc[1][1]=al[1]
		for i in range(2,n):
			if i%2==0:
				cc[0][i]=cc[0][i-2]+al[i]
			else:
				cc[1][i]=max(cc[1][i-2],cc[0][i-3])+al[i]
		return max(cc[0][-2], cc[1][-1])
		
	else:
		cc = [[0]*n,[0]*n, [0]*n]
		cc[0][0]=al[0]
		cc[1][1]=al[1]
		cc[0][2]=al[2]+al[0]
		cc[2][2]=al[2]
		for i in range(3, n):
			if i % 2 ==1:
				cc[1][i]=max(cc[1][i-2],cc[0][i-3])+al[i]
			else:
				cc[0][i]=cc[0][i-2]+al[i]
				cc[2][i]=max(cc[0][i-4],cc[1][i-3],cc[2][i-2])+al[i]
		return max(cc[0][-3],cc[1][-2],cc[2][-1])
				
	
		
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
al = []
g = []
k = []
g0 = 0
k0 = 0
for i in range(n):
    if i % 2 == 0:
        k0 += a[i]
        k.append(k0)
    else:
        g0 += a[i]
        g.append(g0)
if n % 2 == 0:
    al.append(g[n//2-1])
    al.append(k[n//2-1])
    for i in range(n):
        if i % 2 == 0 and i < n-2:
            now = i//2
            al.append(k[now]+g[-1]-g[now])
else:
    
    al.append(g[-1])
    d = a[1]
    for i in range(n):
        if i % 2 == 0:
            al.append(k[-1]-a[i])
        else:
            now = (i-1)//2
            if i > 1 and i < n-2:
                
                al.append(max(g[-1]-g[now],k[-1]-k[now+1])+max(d,k[now-1])+a[i])
                d = max(d+a[i],k[now-1]+a[i])
            elif i == 1:
                al.append(a[i]+max(g[-1]-g[now],k[-1]-k[now+1]))
                d = max(a[i],a[0])
            else:
                al.append(a[i] + max(d,k[now-1]))

print(max(al))

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



















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):
INF = 10 ** 15

N = int(input())
As = list(map(int, input().split()))
As.append(-INF)

INF = 10 ** 15
dp = [[-INF] * (N//2) for _ in range(3)]
dp[0][0] = As[0]
dp[1][0] = As[1]
dp[2][0] = As[2]

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

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

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
INF = 10**18
dp_use = [-INF] * 5
dp_not_use = [-INF] * 5
dp_not_use[0] = 0

for a in A:
    tmp_use = [-INF] * 5
    tmp_not_use = [-INF] * 5
    for current_dif in range(-3,2):
        if current_dif-1 >= -3:
            tmp_use[current_dif] = dp_not_use[current_dif - 1] + a
        if current_dif+1 < 2:
            tmp_not_use[current_dif] = max(dp_use[current_dif+1], dp_not_use[current_dif+1])
    dp_use = tmp_use
    dp_not_use = tmp_not_use
dif = n//2 - (n-n//2)
print(max(dp_use[dif], dp_not_use[dif]))

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    A=list(map(int,input().split()))
    A_=[0]*n
    for i in range(n):
        if i%2==0:
            A_[i]=A[i]
        else:
            A_[i]==0
    for i in range(n-1):
        A_[i+1]+=A_[i]
    dp=[0]*n
    dp[1]=max(A[0],A[1])
    for i in range(2,n):
        if i%2==0:
            dp[i]=max(dp[i-2]+A[i],dp[i-1])
        else:
            dp[i]=max(dp[i-2]+A[i],A_[i-1])
    print(dp[n-1])
if __name__ == '__main__':
    main()