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):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N = getN()
A = getList()













if N % 2 == 0:
    dp = [[-float('inf')] * 2 for i in range(N)]
    dp[0][0] = A[0]
    dp[1][0] = A[1]
    for i in range(2, N):
        for j in range(1, -1, -1):
            if j == 0:
                dp[i][j] = max(dp[i][j], dp[i - 2][j] + A[i])
            elif j == 1 and i - 3 >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 2][j] + A[i])
            if i - 3 >= 0 and j - 1 >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 3][j - 1] + A[i])
    
    print(max(dp[-2][0], dp[-1][0], dp[-1][1]))

else:
    dp = [[-float('inf')] * 3 for i in range(N)]
    dp[0][0] = A[0]
    dp[1][0] = A[1]
    for i in range(2, N):
        for j in range(2, -1, -1):
            if j == 0:
                dp[i][j] = max(dp[i][j], dp[i - 2][j] + A[i])
            elif j >= 1 and i - 3 >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 2][j] + A[i])
            if i - 3 >= 0 and j - 1 >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 3][j - 1] + A[i])
    opt_1 = [A[i] for i in range(N) if i % 2 == 0]
    opt_2 = [A[i] for i in range(N) if i % 2 == 1]
    
    
    
    print(max(dp[-1][2], dp[-1][1], dp[-2][1], sum(opt_1) - min(opt_1), sum(opt_2)))

Solution (Python):
from itertools import accumulate
n = int(input())
A = list(map(int, input().split()))
L = [0]
R = []
min_L = float("inf")
for i, a in enumerate(A):
  b = A[-(i+1)]
  if i%2 == 0:
    L.append(a)
  else:
    R.append(a)
R.append(0)
L = list(accumulate(L))
R = list(accumulate(R[::-1]))[::-1]
ans = -float("inf")
if n%2:
  def f(A):
    temp = 0
    left = 0
    right = 0
    for i in range(2, n, 2):
      temp += A[i]
    res = max(ans, temp)
    for i in range(1, n//2):
      temp -= A[i*2]
      left, right = left+A[2*(i-1)], max(left, right)+A[2*(i-1)+1]
      res = max(res, temp+max(left, right))
    return res
  ans = max(f(A), f(A[::-1]))
  temp = 0
  for i in range(1, n, 2):
    temp += A[i]
  ans = max(ans, temp)
else:
  for l, r in zip(L, R):
    ans = max(ans, l+r)
print(ans)

Solution (Python):
from itertools import accumulate
n = int(input())
A = list(map(int, input().split()))
L = [0]
R = []
min_L = float("inf")
for i, a in enumerate(A):
  b = A[-(i+1)]
  if i%2 == 0:
    L.append(a)
  else:
    R.append(a)
R.append(0)
L = list(accumulate(L))
R = list(accumulate(R[::-1]))[::-1]
ans = -float("inf")
if n%2:
  def f(A):
    temp = 0
    left = 0
    right = 0
    for i in range(2, n, 2):
      temp += A[i]
    res = max(ans, temp)
    for i in range(1, n//2):
      temp -= A[i*2]
      left, right = left+A[2*(i-1)], max(left, right)+A[2*(i-1)+1]
      res = max(res, temp+max(left, right))
    return res
  ans = max(f(A), f(A[::-1]))
  temp = 0
  for i in range(1, n, 2):
    temp += A[i]
  ans = max(ans, temp)
else:
  for l, r in zip(L, R):
    ans = max(ans, l+r)
print(ans)

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

dp0, dp1, dp2 = [0] * (N + 1), [0] * (N + 1), [0] * (N + 1)
dp0[0] = A[0]
dp1[1] = A[1]
dp2[2] = A[2]

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

if N % 2:
    print(max(dp0[N - 3], dp1[N - 2], dp2[N - 1]))
else:
    print(max(dp0[N - 2], dp1[N - 1]))

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

Solution (Python):
from collections import defaultdict
n = int(input())
m = n//2
INF = 10**18
dp = [defaultdict(lambda: -INF)for _ in range(n+2)]
for i, a in enumerate(map(int, input().split()), 2):
    for j in range(max(1, i//2-1), -(-i//2)+1):
        if j-1 == 0:
            dp[i-2][j-1] = 0
        dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+a)

print(dp[n+1][m])

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

inf = float('inf')


if n % 2 == 0:
    l_even = [0]
    l_odd = [0]
    for i in range(n):
        if i % 2 == 0:
            l_even.append(l_even[-1] + a[i])
        else:
            l_odd.append(l_odd[-1] + a[i])
    ans = -inf
    for i in range(n // 2 + 1):
        if ans < l_even[i] + l_odd[-1] - l_odd[i]:
            ans = l_even[i] + l_odd[-1] - l_odd[i]
    print(ans)
    exit()




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

print(max(dp))

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


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


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


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


print(dp[n])

Solution (Python):
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def odd(A):
    oddi=np.array(A[::2],dtype=np.int64)
    eveni=np.array(A[1::2],dtype=np.int64)
    left=np.cumsum(oddi[:-1]-eveni)
    left=np.insert(left,0,0)
    right=np.cumsum(oddi[:0:-1]-eveni[::-1])[::-1]
    right=np.append(right,0)
    tmp=np.max(np.maximum.accumulate(left)+right)
    return tmp+np.sum(eveni)

def even(A):
    left=np.array([0]+A[::2],dtype=np.int64)
    right=np.array(A[1::2]+[0],dtype=np.int64)[::-1]
    return np.max(left.cumsum()+right.cumsum()[::-1])

def main():
    n=int(input())
    A=list(map(int, input().split()))
    if n%2==1:
        print(odd(A))
    else:
        print(even(A))


if __name__ == '__main__':
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


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


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
A = IL()

if N%2 == 0:
  B = [0]
  W = [0]
  for i in range(N//2):
    B.append(B[-1]+A[i*2])
  for i in range(N//2):
    W.append(W[-1]+A[N-1-i*2])
  ans = [B[i]+W[N//2-i] for i in range(N//2+1)]
  print(max(ans))
else:
  A.append(-INF)
  dp = [[0,0,0,0] for i in range(N//2+2)]
  for i in range(N//2+1):
    a,b = A[i*2],A[i*2+1]
    dp[i+1][0] = dp[i][0] + a
    dp[i+1][1] = max(dp[i][0],dp[i][1]) + b
    dp[i+1][2] = max(dp[i][0],dp[i][1])
    if i != 0:
      dp[i+1][3] = max(dp[i][2],dp[i][3]) + a
  print(max(dp[-1][1:]))

Solution (Python):
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def odd(A):
    oddi=np.array(A[::2],dtype=np.int64)
    eveni=np.array(A[1::2],dtype=np.int64)
    left=np.cumsum(oddi[:-1]-eveni)
    left=np.insert(left,0,0)
    left=np.append(left,0)
    right=np.cumsum(oddi[:0:-1]-eveni[::-1])[::-1]
    right=np.insert(right,0,0)
    right=np.append(right,0)
    tmp=np.max(np.maximum.accumulate(left)+right)
    return tmp+np.sum(eveni)

def even(A):
    left=np.array([0]+A[::2],dtype=np.int64)
    right=np.array(A[1::2]+[0],dtype=np.int64)[::-1]
    return np.max(left.cumsum()+right.cumsum()[::-1])

def main():
    n=int(input())
    A=list(map(int, input().split()))
    if n%2==1:
        print(odd(A))
    else:
        print(even(A))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    if N % 2 == 0:
        dp = [[0]*2 for _ in range(N//2 + 1)]
        for i in range(N//2):
            dp[i+1][0] = dp[i][0] + A[2*i]

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

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

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

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

        print(max(dp[-1]))


if __name__ == '__main__':
    main()

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

C = [0 for _ in range(N)] 
D = [0 for _ in range(N)] 
E = [0 for _ in range(N)] 

E[0] = a[0]

for i in range(1,N):
  if i % 2 == 0:
    C[i] = max(C[i-2]+a[i],D[i-1])
    E[i] = E[i-2] + a[i]
  else:
    D[i] = max(D[i-2]+a[i],E[i-1])

if N % 2 == 0:
  print(D[N-1])
else:
  print(C[N-1])

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n=II()
	A=LI()

	X=[-10**10]*(n+1)
	Y=[-10**10]*(n+1)
	X[0]=0
	Y[1]=A[0]
	X[1]=0

	for i in range(2,n+1):
		if i%2==0:
			X[i]=max(Y[i-1],X[i-2]+A[i-1])
		else:
			X[i]=max(X[i-1],X[i-2]+A[i-1])
			Y[i]=Y[i-2]+A[i-1]
	print(X[n])




















if __name__ == "__main__":
	main()

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n=II()
	A=LI()

	X=[-10**10]*(n+1)
	Y=[-10**10]*(n+1)
	X[0]=0
	Y[1]=A[0]
	X[1]=0

	for i in range(2,n+1):
		if i%2==0:
			X[i]=max(Y[i-1],X[i-2]+A[i-1])
		else:
			X[i]=max(X[i-1],X[i-2]+A[i-1])
			Y[i]=Y[i-2]+A[i-1]
	print(X[n])




















if __name__ == "__main__":
	main()

Solution (Python):
P,M,A,I=input,max,int,-10**9
n,a=A(P()),list(map(A,P().split()))
x,y,z=0,I,I
for i,L in enumerate(a):
 if i%2:z=M(y,z);y+=L
 else:y=M(x,y);x+=L;z+=L
print(M(y,z)if n%2else M(x,y))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
  dp = [[0]*2 for _ in range(N)] 
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  for i in range(2,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3>=0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
  ans = max(dp[-2][0],dp[-1][1])
  print(ans)

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

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

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

if n%2 == 1:
    dp = [ [0]*4 for _ in range(n//2+1) ] 

    for i in range(n//2):
        dp[i+1][0] = dp[i][0] + al[i*2]
        dp[i+1][1] = max(dp[i][1]+al[i*2+1], dp[i][0]+al[i*2+1])
        dp[i+1][2] = max(dp[i][2]+al[i*2+2], dp[i][0]+al[i*2+2])
        dp[i+1][3] = max(dp[i][3]+al[i*2+2], dp[i][1]+al[i*2+2])
    ans = max(dp[-1])
    print(ans)

else:
    dp = [ [0]*2 for _ in range(n//2+1) ] 
    for i in range(n//2):
        dp[i+1][0] = dp[i][0] + al[i*2]
        dp[i+1][1] = max(dp[i][1]+al[i*2+1], dp[i][0]+al[i*2+1])
    ans = max(dp[-1])
    print(ans)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

N = int(input())
a = [0] + list(map(int, input().split()))

o = [a[2*i+1] for i in range(N//2)]
o = list(itertools.accumulate(o))

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

dp[0] = dp[1] = 0
dp[2] = max(a[1], a[2])
if N > 2: dp[3] = max([a[1], a[2], a[3]])

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

print(dp[N])

Solution (Python):

def resolve():
    INF = float("-inf")
    N = int(input())
    A = list(map(int, input().split()))

    skip = 1 + N % 2
    
    dp = [[INF] * (skip + 2) for _ in range(N + 1)]
    dp[0][0] = 0

    for i in range(N):
        for j in range(skip + 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][skip])


if __name__ == "__main__":
    resolve()

Solution (Python):
import copy

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

k = 1 + n%2
INF = 10**18
dp = [[-INF]*4 for i in range(n+5)]
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 = copy.deepcopy(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()))
a.insert(0, 0)
dp = [[0] * (n + 1) for _ in range(3)]
for i in range(n % 2 + 2):
    for j in range(1 + i, n + i, 2):
        if i == 0:
            if j == 1:
                dp[i][j] = a[j]
            else:
                dp[i][j] = dp[i][j - 2] + a[j]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 2] + a[j])
ans = dp[n % 2 + 1][n]
print(ans)

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

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]

x, y, z = A[0], A[1], 0
for i in range(2, N):
    if i % 2 == 0:
        z = z + A[i]
        y = max(y, x)
        x = x + A[i]
    else:
        z = max(y, z)
        y = y + A[i]
        x = x

if N % 2 == 0:
    print(max(x, y))
else:
    print(max(y, z))

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()



class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo


show_flg=False
show_flg=True

ans=0


n=I()
a=LI()

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

dp=[[-inf]*3for i in range(n)]
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=a[2]
N=(n)//2

for i in range(n):
    dp[i][2]=max([dp[i-2-j][2-j]+a[i] for j in range(3) if i-2-j>=0 and (i)//2<=N]+[dp[i][2]])
    dp[i][1]=max([dp[i-2-j][1-j]+a[i] for j in range(2) if i-2-j>=0 and (i+1)//2<=N]+[dp[i][1]])
    dp[i][0]=max([dp[i-2-j][j]+a[i] for j in range(1) if i-2-j>=0 and (i+1+1)//2<=N]+[dp[i][0]])

ans=max(dp[n-1][:]+dp[n-2][:2]+dp[n-3][:1])
print(ans)

Solution (Python):
def main():
    import sys
    import numpy as np
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))
    inf = 1e18
    k = n%2 + 1
    dp = np.full((n+1, k+2), -inf, dtype=int)
    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])

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    INF = 10 ** 18
    N = int(input())
    A = list(map(int, input().split(' ')))
    K = 1 + N % 2  
    
    dp = [[- INF for _ in range(K + 1)] for _ in range(N + 1)]
    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])


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate
N, *A = map(int, open(0).read().split())

INF = 1 << 60
dp = [[-INF]*2 for _ in [0]*N]
dp[0][0] = 0

if N & 1:
    for i, a in enumerate(A):
        for j in range(i//2+1, i//2-1, -1):
            dp[j][0] = max(dp[j][0], dp[j][1])
            if j > 0:
                dp[j][1] = dp[j-1][0] + a
else:
    for i, a in enumerate(A):
        for j in range(i//2+1, (i+1)//2-1, -1):
            dp[j][0] = max(dp[j][0], dp[j][1])
            dp[j][1] = dp[j-1][0] + a

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

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

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

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

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

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
AS = LI()
DP = {}
DP[(0, 0)] = 0

mm = -(10**18)
for i in range(N):
    NX = {}
    for ((cnt, isUsed), value) in DP.items():
        if isUsed:
            if cnt >= (i // 2 - 5):
                NX[(cnt, 0)] = max(value, NX.get((cnt, 0)) or mm)
        else:
            if cnt >= (i // 2 - 5):
                NX[(cnt, 0)] = max(value, NX.get((cnt, 0)) or mm)
            if cnt >= (i // 2 - 5):
                NX[(cnt+1, 1)] = max(value + AS[i],
                                     NX.get((cnt+1, 1)) or mm)
    DP = NX
    

res = -(10**18)
for ((cnt, _), value) in DP.items():
    if cnt == N//2:
        res = max(res, value)
print(res)

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
INF = 10 ** 18


dp_use = [-INF] * 4
dp_not_use = [-INF] * 4
dp_not_use[0] = 0

for a in A:
    tmp_use = [-INF] * 4
    tmp_not_use = [-INF] * 4
    for current_diff in range(-2,2):
        if current_diff - 1 >= -2:
            tmp_use[current_diff] = dp_not_use[current_diff-1] + a
        if current_diff + 1 < 2:
            tmp_not_use[current_diff] = max(dp_use[current_diff+1],dp_not_use[current_diff+1]) 
    dp_use = tmp_use
    dp_not_use = tmp_not_use

diff = -1 + (N+1) % 2 
print(max(dp_use[diff],dp_not_use[diff]))

Solution (Python):
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

dp = defaultdict(lambda: -float('inf'))
dp[(0, 0, 0)] = 0

for i, a in enumerate(A, start=1):
    j = i // 2
    for x in range(j - 1, j + 2):
        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 numpy as np
import itertools

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

if N%2==0:
    left = np.cumsum([0]+A[::2])
    right = np.cumsum([0]+A[::-2])[::-1]
    ans = max(left+right)
else:
    left = np.cumsum([0] + A[:-1:2])
    mid_left = np.cumsum([0]+A[-2::-2])[::-1]
    mid_right = np.cumsum([0]+A[1::2])
    right = np.cumsum([0] + A[:1:-2])[::-1]

    left_sum = left+mid_left
    left_max = np.zeros(N//2+1, dtype=int)
    left_max[0] = left_sum[0]
    for i in range(1, N//2+1):
        left_max[i] = max(left_max[i-1], left_sum[i])
    left_max -= mid_left

    right_sum = right + mid_right
    right_max = np.zeros(N//2 + 1, dtype=int)
    right_max[-1] = right_sum[-1]
    for i in range(N//2-1, -1, -1):
        right_max[i] = max(right_max[i + 1], right_sum[i])
    right_max -= mid_right

    ans = max(left_max+right_max)


print(ans)

Solution (Python):
INF = 10**18

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

if N % 2 == 0:
    od = [0 for _ in range(N // 2 + 1)]
    ev = [0 for _ in range(N // 2 + 1)]

    for i in range(N):
        if i % 2 == 0:
            od[i // 2 + 1] = od[i // 2] + A[i]
        else:
            ev[~(i // 2 + 1)] = ev[~(i // 2)] + A[~i + 1]

    res = -INF

    for i in range(N // 2 + 1):
        res = max(res, od[i] + ev[i])

    print(res)

else:
    dp = [[[-INF for k in range(2)] for j in range(3)] for i in range(N + 1)]
    dp[0][0][0] = 0

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

    res = -INF

    for j in range(1, 3):
        for k in range(2):
            if k == 0 and j == 2:
                continue
            res = max(res, dp[N][j][k])

    print(res)

Solution (Python):

from itertools import product
import sys
INF = 10**16
def main(N, A):
    dp = [[[-INF] * 2 for __ in range(3)] for _ in range(N + 1)]
    dp[0][1][0] = dp[0][2][0] = 0
    for i in range(1, N + 1):
        pi = ((i - 1) // 2 - 1, (i - 1) // 2, i // 2)
        ni = (i // 2 - 1, i // 2, (i + 1) // 2)
        for pii, nii, pk, nk in product(range(3), range(3), range(2), range(2)):
            pj, nj = pi[pii], ni[nii]
            if pj > nj or pj + 2 <= nj: continue
            if pj == nj and nk == 1: continue
            if pj < nj and nk == 0: continue
            if pk == 1 and nk == 1: continue
            if dp[i - 1][pii][pk] == -INF: continue
            dp[i][nii][nk] = max(dp[i][nii][nk], dp[i - 1][pii][pk] + (A[i - 1] if nk == 1 else 0))
    ans = -INF
    for k in range(2):
        ans = max(ans, dp[N][1][k])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
inf = 10**18

x = N % 2 + 1
dp = [[-inf] * 4 for _ in range(N + 10)]
dp[0][0] = 0
for i, a in enumerate(A):
    for j in range(x + 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
        dp[i + 1][j] = max(dp[i + 1][j], now)

print(dp[N][x])