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):
from math import ceil, floor


memo = {}


def dp(i, j):
    if (i, j) in memo:
        return memo[(i, j)]
    else:
        return float("inf")*-1


def main():
    n = int(input())
    A = [0] + list(map(int, input().split()))
    memo[(0, 0)] = 0
    memo[(1, 1)] = A[1]
    memo[(1, 0)] = 0
    for i in range(2, n + 1):
        for j in range(max(floor(n/2) - ceil((n-i)/2) - 1, 0), floor(i/2) + 5):
            
            if (i, j) in memo:
                memo[(i, j)] = max(
                    [dp(i, j), A[i] + dp(i - 2, j - 1), A[i] + dp(i - 3, j - 1)])
            else:
                memo[(i, j)] = max(A[i] + dp(i - 2, j - 1),
                                   A[i] + dp(i - 3, j - 1))
            
            if (i - 1, j) in memo:
                memo[(i, j)] = max(dp(i - 1, j), dp(i, j))

    print(dp(n, floor(n/2)))
    return
if __name__ == "__main__":
    main()

Solution (Python):
INF=float('inf')
def solve1():
    dp=[[-INF]*2 for i in range(N+1)]
    dp[0][0]=0;dp[1][0]=A[0];dp[2][1]=A[1]
    for i in range(N):
        if dp[i+1][0]==-INF:
            if i-1>=0:
                dp[i+1][0]=max(dp[i+1][0],dp[i-1][0]+A[i])
        if dp[i+1][1]==-INF:
            if i-1>=0:
                dp[i+1][1]=max(dp[i+1][1],dp[i-1][1]+A[i])
            if i-2>=0:
                dp[i+1][1]=max(dp[i+1][1],dp[i-2][0]+A[i])
    print(max(dp[N][1],dp[N-1][0]))
    return
def solve2():
    dp=[[-INF]*3 for i in range(N+1)]
    dp[0][0]=0;dp[1][0]=A[0];dp[2][1]=A[1];dp[3][2]=A[2]
    for i in range(N):
        if dp[i+1][0]==-INF:
            if i-1>=0:
                dp[i+1][0]=max(dp[i+1][0],dp[i-1][0]+A[i])
        if dp[i+1][1]==-INF:
            if i-1>=0:
                dp[i+1][1]=max(dp[i+1][1],dp[i-1][1]+A[i])
            if i-2>=0:
                dp[i+1][1]=max(dp[i+1][1],dp[i-2][0]+A[i])
        if dp[i+1][2]==-INF:
            if i-1>=0:
                dp[i+1][2]=max(dp[i+1][2],dp[i-1][2]+A[i])
            if i-2>=0:
                dp[i+1][2]=max(dp[i+1][2],dp[i-2][1]+A[i])
            if i-3>=0:
                dp[i+1][2]=max(dp[i+1][2],dp[i-3][0]+A[i])
    print(max(dp[N][2],dp[N-1][1],dp[N-2][0]))
    return

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

if N%2==0:
    solve1()
else:
    solve2()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

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

    dp=[0 for _ in range(N+1)]
    dp[1]=0
    x=A[0]
    for i,a in enumerate(A[1:],2):
        if i%2!=0:
            dp[i]=max(a+dp[i-2],dp[i-1])
            x+=a
            continue
        dp[i]=max(a+dp[i-2],x)
    print(dp[-1])





if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
n = int(input())
a = list(map(int,input().split()))
dp = np.full((2, n//2 + 1), -10**18, dtype=np.int64)
"""
dp[i][j] := iは偶奇, jは何個決めるか
"""
dp[0][0] = 0
dp[1][0] = 0
for i in range(n):
	k = i % 2
	for j in [2, 1, 0]:
		if i//2+j <= n//2:
			if i//2-1+j >= 0:
				dp[k][i//2+j] = np.maximum(dp[1-k][i//2+j], dp[k][i//2-1+j]+a[i])

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

Solution (Python):
def main():
    import os
    import sys
    from io import BytesIO, IOBase
    
    BUFSIZE = 8192
    
    
    class FastIO(IOBase):
        newlines = 0
    
        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None
    
        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()
    
        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()
    
        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)
    
    
    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")
    
    
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

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

    from collections import defaultdict

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

    for i in range(1, n + 1):
        max_j = i//2 if i % 2 == 0 else i//2 + 1
        min_j = n//2 - (n - i)//2 if (n - i) % 2 == 0 else n//2 - ((n - i)//2 + 1)
        for j in range(min_j, max_j + 1):
            dp[(i, j, 0)] = max(dp[(i - 1, j, 0)], dp[(i - 1, j, 1)])
            dp[(i, j, 1)] = dp[(i - 1, j - 1, 0)] + a[i - 1]
    print(max(dp[(n, n//2, 0)], dp[(n, n//2, 1)]))
main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]

    from collections import defaultdict

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

    for i in range(1, n + 1):
        max_j = i//2 if i % 2 == 0 else i//2 + 1
        min_j = n//2 - (n - i)//2 if (n - i) % 2 == 0 else n//2 - ((n - i)//2 + 1)
        for j in range(min_j, max_j + 1):
            dp[(i, j, 0)] = max(dp[(i - 1, j, 0)], dp[(i - 1, j, 1)])
            dp[(i, j, 1)] = dp[(i - 1, j - 1, 0)] + a[i - 1]
    print(max(dp[(n, n//2, 0)], dp[(n, n//2, 1)]))
solve()

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








def solve(start_point):
  for idx, value in enumerate(a[start_point:]):
    idx = idx+start_point
    if idx%2!=0:
      partial_solution[idx][0] = max(partial_solution[idx-1][0], partial_solution[idx-1][1])
      partial_solution[idx][1] = a[idx] + max(partial_solution[idx-2][0], partial_solution[idx-2][1])
      partial_solution[idx][2] = max(partial_solution[idx-1][2], partial_solution[idx-1][3])
      partial_solution[idx][3] = a[idx] + partial_solution[idx-1][0]
    else:
      partial_solution[idx][0] = max(partial_solution[idx-1][2], partial_solution[idx-1][3])
      partial_solution[idx][1] = a[idx] + partial_solution[idx-1][0]
      partial_solution[idx][2] = float('-inf')
      partial_solution[idx][3] = a[idx] + partial_solution[idx-1][2]
  if n%2==0:
    return(max(partial_solution[n-1][2], partial_solution[n-1][3]))
  return(max(partial_solution[n-1][0], partial_solution[n-1][1]))
partial_solution = [[float('-inf') for _ in range(4)] for _ in range(len(a))]
partial_solution[0] = [0, float('-inf'), float('-inf'), a[0]]



print(solve(start_point=1))

Solution (Python):

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

    
    
    skip = 1 + N % 2;

    
    dp = [[INF] * (skip + 1) for _ in range(N + 2)]
    dp[0][0] = 0
    for i in range(N + 1):
        for j in range(skip + 1):
            if j < skip:
                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])
    
    
    print(dp[N + 1][skip])


if __name__ == "__main__":
    resolve()

Solution (Python):
from sys import stdin
n = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))


def naive_2D_dp(n, nums):
    

    

    dp = [[0]*(n//2 + 1) for i in range(n+1)]

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

    
    dp[1][1] = nums[0]

    for i in range(1, n+1):
        for j in range(1, i//2 + 1):
            dp[i][j] = max(nums[i-1] + (dp[i-2][j-1] if i>1 and j>0 else 0), dp[i-1][j] if i>0 else 0)

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



def oneD_dp(n, nums):
    


    
    

    

    
    oddpref = [0]*(n+1)
    oddpref[1] = nums[0]

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

oneD_dp(n, nums)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dp=defaultdict(int)

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

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

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

if n%2==0:
    

    
    
    dp=[[-10**9]*2 for _ in range(n)]

    for i in range(n):
        if i<2:
            dp[i][0]=a[i]

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

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

else:
    

    
    
    dp=[[-10**9]*3 for _ in range(n)]

    for i in range(n):
        if i<2:
            dp[i][0]=a[i]

        if i>=2:
            dp[i][0]=dp[i-2][0]+a[i]
        
        if i>=3:
            dp[i][1]=max(dp[i-2][1]+a[i],dp[i-3][0]+a[i])
            
        if i>=4:
            dp[i][2]=max([dp[i-2][2]+a[i],dp[i-3][1]+a[i],dp[i-4][0]+a[i]])
    
    print(max([dp[-1][2],dp[-1][1],dp[-1][0]-a[0],dp[-1][0]-a[-1]]))

Solution (Python):


import sys
sys.setrecursionlimit(300000)
from pprint import pprint


def solve(N: int, A: "List[int]"):
    memo = [{} for _ in range(N + 1)]
    def rec(idx, rest, can_use=True):
        k = (rest, can_use)
        if rest * 2 >= N - idx + 2:
            return 0
        if rest == 0:
            return 0
        if k in memo[idx]:
            return memo[idx][k]

        ret = 0
        if not can_use:
            ret = rec(idx + 1, rest)
        elif rest * 2 > (N - idx):
            ret = A[idx] + rec(idx + 1, rest - 1, False)
        else:
            a = A[idx] + rec(idx + 1, rest - 1, False)
            b = rec(idx + 1, rest)
            ret = max(a, b)
        memo[idx][k] = ret
        return ret
    ret = rec(0, N // 2)
    print(ret)
    return

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

if __name__ == '__main__':
    main()

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

dp = [[-10**18 for i in range(N//2+1)] for j in range(2)]

dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0

for i in range(2,N+1):
    high = min(N//2, i//2+10)
    low = max(0,i//2-10)
    for j in range(high,low,-1):
        dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1] + A[i-1])
print(dp[N%2][N//2])

Solution (Python):
from collections import defaultdict

N = int(input())
*A, = map(int, input().split())
INF = 10**20
dp = defaultdict(lambda :-INF)
dp[(0,0,0)] = 0

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

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

Solution (Python):
from collections import defaultdict

N = int(input())
*A, = map(int, input().split())
INF = 10**20
dp = defaultdict(lambda :-INF)
dp[(0,0,0)] = 0

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

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

Solution (Python):
from collections import defaultdict

N = int(input())
*A, = map(int, input().split())
INF = 10**20
dp = [[defaultdict(lambda :-INF) for _ in range(N+1)] for _ in range(2)]
dp[0][0][0] = 0

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

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
dp = [[-10**20 for i in range(3)] for j in range(N+1)]
dp[0][1] = 0
dp[1][1] = 0
dp[1][2] = A[0]

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
dp = [[-10**20 for i in range(3)] for j in range(N+1)]
dp[0][1] = 0
dp[1][1] = 0
dp[1][2] = A[0]

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

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

ret = 0

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

print(ret)

Solution (Python):

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

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

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

dic1 = {0:0}
dic2 = {0:0, 1:a[0]}

for i in range(1, n):
    mini = choice - (n-i+1)//2
    new = {}
    for j in range(mini, (i+2)//2+1):
        if j == 0:
            new[j] = 0
            continue
        if j in dic2:
            new[j] = max(dic2[j], dic1[j-1]+a[i])
        else:
            new[j] = dic1[j-1]+a[i]
    dic1 = dic2
    dic2 = new

print(dic2[choice])

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7



n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    dp = [[-float("inf")] * 2 for i in range(n)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    for i in range(2, n):
        dp[i][0] = dp[i - 2][0] + A[i]
        dp[i][1] = max(dp[i - 2][1], dp[i - 3][0] if i >= 3 else float("-inf")) + A[i]

    
    print(max(dp[-1][1], dp[-2][0]))
else:
    dp = [[-float("inf")]*3 for i in range(n)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    for i in range(2, n):
        dp[i][0] = dp[i-2][0] + A[i]
        dp[i][1] = max(dp[i-2][1], dp[i-3][0] if i>=3 else float("-inf")) + A[i]
        dp[i][2] = max(dp[i-2][2], dp[i-3][1] if i>=3 else float("-inf"), dp[i-4][0] if i>=4 else float("-inf")) + A[i]
        if i == 2:
            dp[i][2] = A[2]

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float("inf")
mod = 10 ** 9 + 7

N = INT()
A = LIST()

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

print(dp[N][1])

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

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

if N>=3:
    dp[2][2] = A[2]

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

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

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

dp0 = 0
dp1 = -INF
dp2 = -INF

for i, a in enumerate(A):
    if i % 2 == 0:
        dp1 = max(dp1, dp0)
        dp0 += a
        dp2 += a
    else:
        dp2 = max(dp2, dp1)
        dp1 += a

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

Solution (Python):
n = int(input())
a = [0]+list(map(int,input().split()))
dp = [[0]*2 for _ in range(n+1)]
dp[1][1] = a[1]
dp[2][1] = max(a[1],a[2])

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = LI()

    if n < 4:
        return max(a)

    dp = [[-inf] * 3 for _ in range(n)]
    for i in range(3):
        dp[i][i] = a[i]

    for i in range(n):
        c = a[i]
        di = dp[i]
        if i > 1:
            d2 = dp[i-2]
            for j in range(3):
                if di[j] < d2[j] + c:
                    di[j] = d2[j] + c
        if i > 2:
            d3 = dp[i-3]
            for j in range(2):
                if di[j+1] < d3[j] + c:
                    di[j+1] = d3[j] + c
        if i > 3:
            d4 = dp[i-4]
            for j in range(1):
                if di[j+2] < d4[j] + c:
                    di[j+2] = d4[j] + c

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

    r = -inf
    for i in range(3):
        r = max(r, dp[-1-i][2-i])

    return r

print(main())

Solution (Python):
from collections import defaultdict


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

    def default():
        return -float("inf")
    dp = [defaultdict(default) for _ 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):
        dp[i][i//2] = max(dp[i-2][i//2-1] + A[i], dp[i-1][i//2])
        dp[i][i//2+1] = max(dp[i-2][i//2] + A[i], dp[i-1][i//2+1])
    print(dp[N-1][N//2])


if __name__ == "__main__":
    main()

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

dp = [dict() for _ in range(n)]

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

import math
for i in range(2, n):
    k1 = int(math.ceil((i + 1) / 2))
    k2 = k1 - 1

    if i % 2 == 0:
        dp[i][k1] = dp[i-2][k1-1] + a[i]
    else:
        dp[i][k1] = max(dp[i-1][k1], dp[i-2][k1-1] + a[i])

    dp[i][k2] = max(dp[i-1][k2], dp[i-2][k2-1] + a[i])

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

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

INF = 10 ** 18

if N % 2:
    dp = [[-INF for j in range(N)] for i in range(3)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for j in range(N):
        for i in range(3):
            if dp[i][j] == -INF:
                continue
            for k in range(3):
                if i + k < 3 and j + k + 2 < N:
                    dp[i + k][j + k + 2] = max(dp[i + k][j + k + 2], dp[i][j] + A[j + k + 2])
    print(max(max(dp[0][-3:-1]), max(dp[1][-2:]), max(dp[2][-1:])))
    
else:
    dp = [[-INF for j in range(N)] for i in range(2)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    for j in range(N):
        for i in range(2):
            if dp[i][j] == -INF:
                continue
            for k in range(2):
                if i + k < 2 and j + k + 2 < N:
                    dp[i + k][j + k + 2] = max(dp[i + k][j + k + 2], dp[i][j] + A[j + k + 2])
    print(max(max(dp[0][-2:]), max(dp[1][-1:])))

Solution (Python):
from collections import defaultdict
N,*A = map(int, open(0).read().split())
dic1 = defaultdict(lambda :-10**20)
dic2 = defaultdict(lambda :-10**20)
for i in range(-1,N):
  dic1[(i,0)] = 0
  dic2[(i,0)] = 0
for i in range(N):
  for j in range(max(1,N//2-(N-i+1)//2), i//2+2):
    dic1[(i,j)] = max(dic1[(i,j)],dic2[(i-1,j-1)]+A[i])
  for j in range(N//2-(N-i)//2,(i-1)//2+2):
    dic2[(i,j)] = max(dic2[(i-1,j)],dic1[(i-1,j)])
print(max(dic1[(N-1,N//2)],dic2[(N-1,N//2)]))

Solution (Python):
import math
import sys
sys.setrecursionlimit(1000000)

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

memo = {}
def sub_max(n, m):
    if((n, m) in memo):
        return memo[(n, m)]
    
    if(m == 1 and n >= 1):
        memo[(n, m)] = max(A[-n:])
        return memo[(n, m)]

    if(m > math.ceil(n/2)):
        memo[(n, m)] = -float('inf')
        return -float('inf')
    
    res = -float('inf')
    for i in range(3):
        res = max(res, A[-n + i] + sub_max(n - i - 2, m - 1))
    memo[(n, m)] = res
    return res

print(sub_max(N, N//2))

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
k = 1 + n%2
dp = [[-float('inf')] * (k + 2) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(k + 1):
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
        now = dp[i][j]
        if (i + j) % 2 == 0:
            now += a[i]
        dp[i + 1][j] = max(dp[i + 1][j], now)
print(dp[n][k])

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

DP = [0,0,0]
m = N//2*2
if N%2 == 0:
    for i in range(0,m,2):
        DP[0] += A[i]
        DP[1] += A[i+1]
        DP[1] = max(DP[0],DP[1])

    print(DP[1])

else:
    for i in range(0,m,2):
        DP[0] += A[i]
        DP[1] += A[i+1]
        DP[2] += A[i+2]

        DP[1] = max(DP[0],DP[1])
        DP[2] = max(DP[1],DP[2])

    print(DP[2])

Solution (Python):
def solve():
    INF = float('inf')

    def max2(x, y): return x if x >= y else y

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

    dp = [[[-INF]*(2) for j in range(3)] for i in range(N+1)]
    dp[0][2][0] = dp[0][2][1] = 0
    for i, A in enumerate(As):
        if i&1:
            for k in range(2):
                for j in range(3):
                    dp[i+1][j][0] = max2(dp[i+1][j][0], dp[i][j][k])
            for j in range(2):
                dp[i+1][j+1][1] = max2(dp[i+1][j+1][1], dp[i][j][0] + A)
        else:
            for j in range(3):
                dp[i+1][j][1] = max2(dp[i+1][j][1], dp[i][j][0] + A)
            for k in range(2):
                for j in range(1, 3):
                    dp[i+1][j-1][0] = max2(dp[i+1][j-1][0], dp[i][j][k])

    if N&1:
        print(max(dp[-1][1]))
    else:
        print(max(dp[-1][2]))


solve()

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

v1 = 0
v2 = 0
v3 = 0
m = N // 2 *2 
if N % 2 == 0:
  for i in range(0, m, 2):
    v1 += A[i]
    v2 += A[i+1]
    v2 = max(v1,v2)
  print(v2)  

else:
  for i in range(0, m, 2):
    v1 += A[i]
    v2 += A[i+1]
    v3 += A[i+2]
    v2 = max(v1,v2)
    v3 = max(v2,v3)
  print(v3)

Solution (Python):



import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf



import math

import bisect

class Solver:

    def __init__(self, n, a_s):
        self.n = n
        self.a_s = a_s
        self.extra = 1 if self.n % 2 == 0 else 2
        self.dp = self.prepare_dp()

    def prepare_dp(self):
        dp = [None] * (self.n + 1)
        for i, _ in enumerate(dp):
            dp[i] = [-1 * math.inf] * (1 + self.extra)
        dp[0][0] = 0
        return dp

    def run(self):
        extra = 1 + self.n % 2
        for i, a in enumerate(self.a_s):
            for j in range(self.extra):
                self.dp[i + 1][j + 1] = self.dp[i][j]
            for j in range(self.extra + 1):
                v = self.dp[i][j]
                if (i + j) % 2 == 0:
                    v += a
                self.dp[i + 1][j] = max(self.dp[i + 1][j], v)
        
        
        return self.dp[n][extra]



if __name__ == '__main__':
    n = int(input())
    a_s = list(map(int, input().split()))
    ans = Solver(n, a_s).run()
    
    print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
m0 = 0
m1 = 0
m2 = 0

if n%2 == 0:
    for i,ai in enumerate(a):
        if i%2 == 0:
            m0 += ai
        else:
            m1 = max(m0,m1+ai)
    print(max(m0,m1))
else:
    for i,ai in enumerate(a):
        if i%2 == 0:
            if i > 0:
                m2 = max(m2+ai,m1,m0)
            if i < n-1:
                m0 += ai
        else:
            m1 = max(m0,m1+ai)
    print(max(m0,m1,m2))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
import numpy as np
dp=np.full((3,n+1),-pow(10,15))
dp[:,0]=0
dp[1,1]=a[0]
for i in range(2,n+1):
    
    l,r=max(1,i//2-1),(i+1)//2+1
    if i%3==2:
        now,pre,prepre=2,1,0
    elif i%3==0:
        now,pre,prepre=0,2,1
    elif i%3==1:
        now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])