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,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
n = onem()
a = l()


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

    ans = sum(a[0::2])
    ans = max(ans,sum(a[1::2]))
    co = 0
    for i in range(0,n,2):
        if i+1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co)
        co += a[i]

    print(ans)

else:
    po = [a[i] for i in range(n)]
    mi = [-Max for i in range(n)]
    
    for i in range(n-3,-1,-1):
        po[i] += po[i+2]

    ans = sum(a[1::2])
    ans = max(ans,sum(a[0::2]) - a[-1])
    
    l1 = [-Max for i in range(n)]
    for i in range(n):
        if i != n-1:
            l1[i] = po[i+1]

    """
    co = 0
    for i in range(0,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    co = 0
    for i in range(1,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    """

    for i in range(n-1,-1,-1):
        if i == n-1:
            continue
        elif i == n-2:
            mi[i] = l1[i]
        else:
            mi[i] = max(mi[i+2]+a[i],l1[i])


    l1 = mi


    """
    for i in range(n-1,-1,-1):
        if i <= n-3:
            mi[i] = min(mi[i+2],a[i])
        else:
            mi[i] = a[i]
    print(mi)
    """
    
    l2 = [-Max for i in range(n)]
    
    for i in range(n-1,-1,-1):
        l2[i] = po[i]
        
    
    
    co = 0

    for i in range(0,n,2):
        if i + 2 <= n-1:
            
            ans = max(ans,co+l1[i+1],co+l2[i+2])
        elif i+1 <= n-1:
            ans = max(ans,co+l1[i+1])
        else:
            ans = max(ans,co)
        
        co += a[i]
    co = 0
    
    for i in range(1,n,2):
        
        ans = max(ans,co+po[i+1])
        
        co += a[i]
    
    print(ans)

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

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

Solution (Python):
def main():
    from functools import lru_cache
    import sys

    sys.setrecursionlimit(10 ** 7)

    inf = 2 * 10 ** 14 + 1

    N = int(input())
    *a, = map(int, input().split())

    @lru_cache(maxsize=None)
    def recursion(cur, need):
        """
        cur: pickableなindex
        """
        if cur >= N:
            if need == 0:
                return 0
            else:
                return -inf

        rest = N - cur
        if (rest + 1) // 2 < need:
            return -inf

        return max(
            a[cur] + recursion(cur + 2, need - 1),
            recursion(cur + 1, need)
        )

    ans = recursion(0, N // 2)

    print(ans)


if __name__ == '__main__':
    main()

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):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n % 2 == 0:
        dp = [[-10**18]*2, [-10**18]*2]
        dp[0][0] = 0
        for i in range(n):
            dp2 = [[-10**18]*2, [-10**18]*2]
            
            dp2[1][0] = max(dp2[1][0], dp[0][0]+a[i])
            dp2[1][1] = max(dp2[1][1], dp[0][1]+a[i])
            
            dp2[0][1] = max(dp2[0][1], dp[0][0])
            
            dp2[0][0] = max(dp2[0][0], dp[1][0])
            dp2[0][1] = max(dp2[0][1], dp[1][1])
            dp = dp2
        print(max(dp[1][1], dp[0][0]))
        return
    dp = [[-10**18]*3, [-10**18]*3]
    dp[0][0] = 0
    for i in range(n):
        
        dp2 = [[-10**18]*3, [-10**18]*3]
        dp2[1][0] = max(dp2[1][0], dp[0][0]+a[i])
        dp2[1][1] = max(dp2[1][1], dp[0][1]+a[i])
        dp2[1][2] = max(dp2[1][2], dp[0][2]+a[i])
        
        dp2[0][1] = max(dp2[0][1], dp[0][0])
        dp2[0][2] = max(dp2[0][2], dp[0][1])
        
        dp2[0][0] = max(dp2[0][0], dp[1][0])
        dp2[0][1] = max(dp2[0][1], dp[1][1])
        dp2[0][2] = max(dp2[0][2], dp[1][2])
        dp = dp2
    print(max(dp[1][2], dp[0][1]))


main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 20

dp = [{} for i in range(n + 1)]
dp[0][0] = 0

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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n = II()
    a = LI()
    if n == 3:
        print(max(a))
        return
    dp = [[-inf] * 3 for i in range(n + 1)]
    dp[0] = [0, 0, 0]
    dp[1][0] = a[0]
    dp[2][1] = a[1]
    for i in range(3, n+1):
        dp[i][0] = dp[i - 2][0] + a[i-1]
        dp[i][1] = max(dp[i - 2][1], dp[i - 3][0]) + a[i-1]
        dp[i][2] = max(dp[i - 2][2], dp[i - 3][1], dp[i - 4][0]) + a[i-1]
    if n & 1:
        print(max(dp[-3][0], dp[-1][1], dp[-1][2]))
    else:
        print(max(dp[-1][1], dp[-2][0]))
    return



if __name__ == '__main__':
    solve()

Solution (Python):



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

k=0
k1=As[0]
g=0
for i in range(2,N+1):
    if i%2==1:
        k=max(k+As[i-1],g)
        k1=k1+As[i-1]
    if i%2==0:
        g=max(k1,g+As[i-1])
    

ans=g if N%2==0 else k
print(ans)

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

if N%2==0:
  dp=[]
  for i in range(2):
    array=[0]*N
    dp.append(array)
    
  
  dp[0][0]=alist[0]
  dp[1][1]=alist[1]
  for i in range(2,N):
    dp[0][i]=dp[0][i-2]+alist[i]
    dp[1][i]=max(dp[1][i-2]+alist[i],dp[0][i-3]+alist[i])
    
  print(max(dp[0][-2],dp[1][-1]))
else:
  dp=[]
  for i in range(3):
    array=[0]*N
    dp.append(array)

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

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

Solution (Python):
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import defaultdict

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

INF = 10**18
dp_not = defaultdict(lambda : -INF)
dp_take = defaultdict(lambda: -INF)
dp_not[(0,0)] = 0

for i,x in enumerate(A,1):
	j = (i-1)//2
	for n in (j,j+1):
		dp_not[(i,n)] = max(dp_not[(i-1,n)], dp_take[(i-1,n)])
		dp_take[(i,n)] = dp_not[(i-1,n-1)] + x

print(max(dp_not[(N, N//2)], dp_take[(N, N//2)]))

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[-1 * pow(10, 15)] * 3 for _ in range(N)]
    if N == 2:
        return max(A)
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(N):
        if i < 2:
            continue
        dp[i][0] = dp[i-2][0] + A[i]
        if i < 3:
            continue
        dp[i][1] = max(dp[i-3][0], dp[i-2][1]) + A[i]
        if i < 4:
            continue
        dp[i][2] = max(dp[i-4][0], dp[i-3][1], dp[i-2][2]) + A[i]
    if N % 2 == 0:
        return max(dp[-1][1], dp[-2][0])
    else:
        return max(dp[-1][2], dp[-2][1], dp[-3][0])
print(main())

Solution (Python):


N=int(input())
A=list(map(int,input().split()))
INF=10**18

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

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

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

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n = int(input())
A = get_nums_l()


p = 1 if n%2==0 else 2



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

dp[0][0][0] = -999999999999999999
dp[0][1][0] = -999999999999999999
dp[1][0][0] = -999999999999999999
if p == 2:
    dp[0][2][0] = -999999999999999999
    dp[1][1][0] = -999999999999999999



for k in range(n):
    dp[0][0][k+1] = dp[1][0][k] + A[k]
    dp[0][1][k+1] = dp[1][1][k] + A[k]
    dp[1][0][k+1] = max(dp[1][1][k], dp[0][0][k])
    dp[1][1][k+1] = dp[0][1][k]

    if p == 2:
        dp[0][2][k+1] = dp[1][2][k] + A[k]
        dp[1][2][k+1] = dp[0][2][k]
        
        dp[1][1][k+1] = max(dp[1][1][k+1], dp[1][2][k])






ans = [dp[0][0][n], dp[0][1][n], dp[1][0][n], dp[1][1][n]]
if p == 2:
    
    ans.append(dp[1][2][n])
print(max(ans))

Solution (Python):
import sys

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

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

main()

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

dp = np.full((N, 3), 0, dtype=int)

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

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

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if n%2==0:
  dp=[[0 for i in range(2)] for j in range(n)]
  dp[0][0]=a[0]
  dp[1][1]=a[1]
  for i in range(2,n):
    if i==2:
      dp[i][0]=dp[i-2][0]+a[i]
      dp[i][1]=dp[i-2][1]+a[i]
    else:
      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-1][1],dp[n-2][0]))

else:
  dp=[[0 for i in range(3)] for j in range(n)]
  dp[0][0]=a[0]
  dp[1][1]=a[1]
  dp[2][2]=a[2]
  for i in range(2,n):
    if i==2:
      dp[i][0]=dp[i-2][0]+a[i]
      dp[i][1]=dp[i-2][1]+a[i]
    else:
      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],dp[i-4][0])+a[i]
  print(max(dp[n-1][2],dp[n-2][1],dp[n-3][0]))

Solution (Python):





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


memo = [{} for i in range(n)]
memo[0] = {0: 0, 1: a[0]}
memo[1] = {1: max(a[:2])}

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

print(memo[-1][n // 2])

Solution (Python):


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

l = [0] * n 
u = [0] * n 

l[0] = 0
u[0] = a[0]
u[1] = max(a[:2])
l[1] = u[1]






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

print(l[-1])

Solution (Python):
import sys,math,copy,queue,itertools,bisect
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
MOD = 10**9 + 7
INF = 10**15

N = NI()
A = LI()
ans = 0
if N % 2 == 0:
    for i in range(1,N,2):
        ans += A[i]
    x = ans
    for i in range(0,N,2):
        x = x + A[i] - A[i+1]
        ans = max(ans,x)
else:
    dp = [0 for _ in range(3)]
    for i in range(N):
        ai = A[i]
        if i % 2 == 0:
            dp[1] = max(dp[0],dp[1])
            dp[0] = dp[0] + ai
        if i % 2 == 1:
            dp[2] = max(dp[1],dp[2])
            dp[1] += ai
        if i % 2 == 0 and i > 0:
            dp[2] += ai
    ans = max(dp[1],dp[2])
print (ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    
    dp = [0] * N
    dp[1] = max(A[:2])
    odd = A[0]
    
    for i in range(2, N):
        if i % 2 == 0:
            odd += A[i]
            dp[i] = max(dp[i - 2] + A[i], dp[i - 1])
        else:
            dp[i] = max(dp[i - 2] + A[i], odd)
    print(dp[-1])


if __name__ == '__main__':
    solve()

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**20
    N=I()
    A=LI()
    """左から見ていく，i個を見たときに，
    i//2 ±1の範囲なので，状態は3N通り
    """
    
    p1=[-inf]*N
    zero=[-inf]*N
    n1=[-inf]*N
    
    p1[0]=A[0]
    zero[0]=0
    zero[1]=max(A[0],A[1])
    n1[1]=0
    
    for i in range(2,N):
        
        if i%2==0:
            p1[i]=max(p1[i-2]+A[i],p1[i-1])
            zero[i]=max(zero[i-2]+A[i],zero[i-1])
            n1[i]=max(n1[i-2]+A[i],n1[i-1])
        else:
            p1[i]=p1[i-2]+A[i]
            zero[i]=max(zero[i-2]+A[i],p1[i-1])
            n1[i]=max(n1[i-2]+A[i],zero[i-1])
            
    """        
    print(p1)
    print(zero)
    print(n1)"""
    
    print(zero[-1])
    
    
        
        
        

main()

Solution (Python):
n = int(input())
l = list(map(int,input().split()))
dp = [[-float("INF")]*(3) for i in range(n+1)]
dp[0][0] = 0
dp[1][-1] = 0
dp[1][1] = l[0]
for i in range(1,n):  
    dp[i+1][-1] = max(dp[i][0],dp[i-1][-1]+l[i])
    dp[i+1][0] = max(dp[i][1],dp[i-1][0]+l[i])
    dp[i+1][1] = dp[i-1][1]+l[i]
    
print(max(dp[-1][0],dp[-1][-1]))

Solution (Python):
n = int(input())
def main():
    import sys
    input = sys.stdin.readline
    l = list(map(int,input().split()))
    dp = [[-float("INF")]*(3) for i in range(n+1)]
    dp[0][0] = 0
    dp[1][-1] = 0
    dp[1][1] = l[0]
    for i in range(1,n):
        
        dp[i+1][-1] = max(dp[i][0],dp[i-1][-1]+l[i])
        dp[i+1][0] = max(dp[i][1],dp[i-1][0]+l[i])
        dp[i+1][1] = dp[i-1][1]+l[i]
    print(max(dp[-1][0],dp[-1][-1]))

if __name__ == "__main__":
    main()

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

dp0 = [-INF] * (N + 2)
dp1 = [-INF] * (N + 2)
dp2 = [-INF] * (N + 2)
dp0[0] = 0
dp0[1] = 0
dp1[0] = 0
dp1[1] = 0

for i, a in enumerate(A, start=2):
    dp0[i] = dp0[i - 2] + a
    dp1[i] = max(dp1[i - 2] + a, dp0[i - 1])
    dp2[i] = max(dp2[i - 2] + a, dp1[i - 1], dp0[i - 2])

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

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


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

Solution (Python):

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = list(map(int, input().split()))
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    '''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()))
if n%2==1:
    dp=[[0 for j in range(3)] for i 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+1)])
        dp[i+1][1]=max(dp[i][0],dp[i][1])+a[2*(i+1)+1]
        dp[i+1][2]=max(dp[i])+a[2*(i+1)+2]
    print(max(dp[-1]))
if n%2==0:
    dp=[[0 for j in range(2)] for i 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+1)])
        dp[i+1][1]=max(dp[i][0],dp[i][1])+a[2*(i+1)+1]
        
    print(max(dp[-1]))

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

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

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

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

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

print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
dp0 = 0
dp1 = 0
dp2 = 0
for i in range(1,n+1):
  ai = a[i-1]
  if i%2:
    dp1 = max(dp0,dp1)
    dp0 += ai
  if i%2 == 0:
    dp2 = max(dp1,dp2)
    dp1 += ai
  if i >= 3 and i%2:
    dp2 += ai
if n%2 == 0:
  print(max(dp0,dp1))
else:
  print(max(dp1,dp2))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N=int(input())
    A=list(map(int,input().split()))
    dp=[[-INF]*3 for _ in range(N+10)]
    dp[0][0]=0
    for i in range(N+1):
        for j in range(3):
            if j+1<3:
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j])
            if i<N:
                dp[i+2][j]=max(dp[i+2][j],dp[i][j]+A[i])
    if N%2:
        print(dp[N+1][2])
    else:
        print(dp[N+1][1])
    

if __name__ == '__main__':
    main()

Solution (Python):


n = 0
a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		a = [rng(-1 * 10**9, 10**9) for i in range(n)]
		print(n)
		print(' '.join(list(map(str, a))))

def get_answer():
	odd = [0]
	even = [0]
	for i in range(n // 2):
		odd.append(odd[-1] + a[2*i])
		even.append(even[-1] + a[2*i+1])
	if n % 2 == 1:
		odd.append(odd[-1] + a[-1])

	answer = -1 * 10**9 * n
	if n % 2 == 0:
		for i in range(n // 2 + 1):
			answer = max(answer, odd[i] - even[i] + even[-1])
	else:
		even_range = [even[0] - odd[1]]
		for i in range(n // 2):
			add = a[2*i+1] - a[2*i+2]
			min = - a[2*i] + add
			even_range.append(max(even_range[-1] + add, min))
		answer = odd[-1] + max(even_range)
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

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

dp0 = [-INF] * (N + 2)
dp1 = [-INF] * (N + 2)
dp2 = [-INF] * (N + 2)
dp0[0] = 0
dp0[1] = 0
dp1[0] = 0
dp1[1] = 0

for i, a in enumerate(A, start=2):
    dp0[i] = dp0[i - 2] + a
    dp1[i] = max(dp1[i - 2] + a, dp0[i - 1])
    dp2[i] = max(dp2[i - 2] + a, dp1[i - 1], dp0[i - 2])

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

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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
dp = [0 for i in range(3)]
for i in range(1,n+1):
  ai = a[i-1]
  if i%2:
    dp[1] = max(dp[0],dp[1])
    dp[0] += ai
  if i%2 == 0:
    dp[2] = max(dp[1],dp[2])
    dp[1] += ai
  if i >= 3 and i%2:
    dp[2] += ai
if n%2 == 0:
  print(max(dp[0],dp[1]))
else:
  print(max(dp[1],dp[2]))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
dp = [0 for i in range(3)]
for i in range(1,n+1):
  ai = a[i-1]
  if i%2:
    dp[1] = max(dp[0],dp[1])
    dp[0] += ai
  if i%2 == 0:
    dp[2] = max(dp[1],dp[2])
    dp[1] += ai
  if i >= 3 and i%2:
    dp[2] += ai
if n%2 == 0:
  print(max(dp[0],dp[1]))
else:
  print(max(dp[1],dp[2]))

Solution (Python):
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
 
sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

dp = [{} for _ in range(N + 1)]
dp[0] = {0: 0}
dp[1] = {0: 0, 1: A[0]}

for i in range(2, N + 1):
    for j in range(max(0, i // 2 - 2), min(N, i // 2 + 2) + 1):
        candidates = []
        if j - 1 in dp[i - 2]:
            candidates.append(dp[i - 2][j - 1] + A[i - 1])
        if j in dp[i - 1]:
            candidates.append(dp[i - 1][j])
        if len(candidates) > 0:
            dp[i][j] = max(candidates)

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

Solution (Python):
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
 
sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

dp = [{} for _ in range(N + 1)]
dp[0] = {0: 0}
dp[1] = {0: 0, 1: A[0]}

for i in range(2, N + 1):
    for j in range(max(0, i // 2 - 2), min(N, i // 2 + 2) + 1):
        candidates = []
        if j - 1 in dp[i - 2]:
            candidates.append(dp[i - 2][j - 1] + A[i - 1])
        if j in dp[i - 1]:
            candidates.append(dp[i - 1][j])
        if len(candidates) > 0:
            dp[i][j] = max(candidates)

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

Solution (Python):


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

n,*a = [int(i) for i in read().split()]

from itertools import accumulate
if n%2==0:
    a1 = list(accumulate([0]+a[::2]))
    a2 = list(accumulate([0]+a[n-1::-2]))[::-1]
    
    print(max(x+y for x,y in zip(a1,a2)))

else:
    dp0 = [0]*(n+9)
    dp1 = [0]*(n+9)
    dp2 = [0]*(n+9)
    for i in range(n):
        if i%2==0:
            dp0[i] = dp0[i-2]+a[i]
            if i >= 2:
                dp2[i] = max(dp2[i-2],dp1[i-3],dp0[i-4]) + a[i]
        else:
            dp1[i] = max(dp1[i-2],dp0[i-3]) + a[i]
    
    
    
    print(max(dp2[n-1],dp1[n-2],dp0[n-3]))

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))

    if n & 1 == 0:
        res = -INF
        score = sum(A[::2])
        res = max(res, score)
        for i in range(n-1,-1,-1):
            if i & 1:
                score += A[i]
            else:
                score -= A[i]
                res = max(res, score)
        print(res)
        return

    front_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(1, n, 2):
        choose, not_choose = max(choose, not_choose) + A[i], not_choose + A[i-1]
        front_dp[i] = max(choose, not_choose)

    back_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(n-2, -1, -2):
        choose, not_choose = max(choose, not_choose) + A[i], not_choose + A[i+1]
        back_dp[i] = max(choose, not_choose)

    res = -INF
    for i in range(1, n, 2):
        if i + 2 < n:
            res = max(res, front_dp[i] + back_dp[i+2])

    res = max(res, front_dp[-2])
    res = max(res, back_dp[1])

    print(res)
resolve()

Solution (Python):
N = int(input()) + 2
X = [0, 0] + list(map(int, input().split()))
dp = [[0, 0] for _ in range(N)]
for i in range(2, N):
    if i%2:
        dp[i][1] = max(dp[i-2][1] + X[i], dp[i-1][1])
        dp[i][0] = max(dp[i-2][0] + X[i], dp[i-1][0])
    else:
        dp[i][1] = dp[i-2][1] + X[i]
        if i!=2:
            dp[i][0] = max(dp[i-2][0] + X[i], dp[i-1][1])

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