Problem:
 Score : 600 points    Problem Statement Given is an integer sequence A_1, ..., A_N of length N .  We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.  Find the maximum possible sum of the chosen elements.  Here \lfloor x \rfloor denotes the greatest integer not greater than x .      Constraints  2 \leq N \leq 2\times 10^5  |A_i|\leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  ...  A_N       Output Print the maximum possible sum of the chosen elements.        Sample Input 1 6
1 2 3 4 5 6      Sample Output 1 12  Choosing 2 , 4 , and 6 makes the sum 12 , which is the maximum possible value.       Sample Input 2 5
-1000 -100 -10 0 10      Sample Output 2 0  Choosing -10 and 10 makes the sum 0 , which is the maximum possible value.       Sample Input 3 10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000      Sample Output 3 5000000000  Watch out for overflow.       Sample Input 4 27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49      Sample Output 4 295

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

dp_list = [{0, 0}, {0: 0, 1: A[1]}, {0: 0, 1: A[1] if A[1] > A[2] else A[2]}]

for i in range(3, N+1):
    b = (i-1)//2
    f = (i+1)//2
    dp_list.append({})
    for j in range(b, f+1):
        if j in dp_list[i-1]:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i] if dp_list[i -
                                                              2][j-1]+A[i] > dp_list[i-1][j] else dp_list[i-1][j]
        else:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i]

print(dp_list[-1][N//2])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

dp0 = list2d(N+1, 4, -INF)
dp1 = list2d(N+1, 4, -INF)
dp0[0][2] = 0
for i, a in enumerate(A):
    for j in range(4):
        if j != 0:
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp0[i][j])
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp1[i][j])
        if j != 3:
            dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + a)
if N % 2 == 0:
    ans = max(dp0[N][2], dp1[N][2])
else:
    ans = max(dp0[N][1], dp1[N][1])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

SUM=[0]*(N+1)
for i in range(N-1,-1,-1):
    SUM[i]=SUM[i+1]

    if (N-i)%2==1:
        SUM[i]+=A[i]


        
from functools import lru_cache
@lru_cache(maxsize=None)
def calc(i,select):
    rest=N-i

    if rest==0 or select==0:
        return 0

    if rest%2==1 and rest//2+1==select:
        return SUM[i]
    
    elif rest%2==0 and rest//2==select:
        return max(calc(i+1,select),A[i]+calc(i+2,select-1))

    elif rest%2==1 and rest//2==select:
        return max(calc(i+1,select),A[i]+calc(i+2,select-1))

print(calc(0,N//2))

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
totalChooseNum = N // 2
dp = {0 : 0}
for i in range(0, N):
    ai = A[i]
    canChooseNum = (N - i + 1) // 2
    mustChooseNum = max(totalChooseNum - canChooseNum, 0)
    next = {}
    for j in range(mustChooseNum, N):
        if j > 0 and (2 * (j - 1)) in dp:
            next[2 * j + 1] = dp[2 * (j - 1)] + ai
        if 2 * j in dp:
            if 2 * j + 1 in dp:
                next[2 * j] = max(dp[2 * j] , dp[2 * j + 1])
            else:
                next[2 * j] = dp[2 * j]
        elif 2 * j + 1 in dp:
            next[2 * j] = dp[2 * j + 1]
        else:
            break
    dp = next
result = max(dp[totalChooseNum * 2] , dp[totalChooseNum * 2 + 1])
print(result)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    if not n&1:
        dp = a[:2]
        for i in range(2,n)[::2]:
            nd = [-float("inf")]*2
            nd[0] = dp[0]+a[i]
            nd[1] = max(dp)+a[i+1]
            dp = [j for j in nd]
        print(max(dp))
        return
    dp = a[:3]
    dp[0] = a[0]
    dp[1] = a[1]
    dp[2] = a[2]
    for i in range(2,n-1)[::2]:
        nd = [-float("inf")]*3
        nd[0] = dp[0]+a[i]
        nd[1] = max(dp[0],dp[1])+a[i+1]
        nd[2] = max(dp)+a[i+2]
        dp = [j for j in nd]
    print(max(dp))
    return


if __name__ == "__main__":
    solve()

Solution (Python):


import sys
input = sys.stdin.buffer.readline

def main():
    n=int(input())
    a=list(map(int,input().split()))
    
    if n<4:
        print(max(a))
        sys.exit()

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

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

main()

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

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

def main():
    n=int(input())
    a=list(map(int,input().split()))
    
    
    if n<4:
        print(max(a))
        sys.exit()

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

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

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

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

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

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

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

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

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

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

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

INF = 10 ** 18

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

import sys
input = sys.stdin.readline
INF = 10**18
 
n = int(input())
a = [int(item) for item in input().split()]
 
 

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

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

dp = [{} for __ in range(N+1)]

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

for i in range(2, N+1):
    for j in range((i-1)//2, (i+1)//2+1):
        app = (dp[i-2][j-1] if j-1 in dp[i-2] else -float('inf')) + A[i-1]
        napp = dp[i-1][j] if j in dp[i-1] else -float('inf')
        dp[i][j] = max(app, napp)

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

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 20
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
from collections import defaultdict
dy = (-1,0,1,0)
dx = (0,1,0,-1)

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

    dp = [{(i - 1)//2: -INF, (i + 1)//2: -INF} for i in range(n + 1)]
    dp[0][0] = 0
    dp[1][0] = 0
    dp[1][1] = a[0]
    for i in range(1,n):
        if i%2 == 1:
            m1,m2 = (i + 2)//2,i//2
            dp[i + 1][m1] = max(dp[i - 1][m1 - 1] + a[i],dp[i][m1])
            dp[i + 1][m2] = max(dp[i - 1][m2 - 1] + a[i],dp[i][m2])
        else:
            m1,m2 = (i + 2)//2,i//2
            dp[i + 1][m1] = dp[i - 1][m1 - 1] + a[i]
            dp[i + 1][m2] = max(dp[i - 1][m2 - 1] + a[i],dp[i][m2])

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

if __name__ =='__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
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 LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	a = LI()
	a = [0]+a
	dp_t = defaultdict(lambda: -10**18)
	dp_f =  defaultdict(lambda: -10**18)
	dp_f[(0,0)]=0
	for i in range(1,n+1):
		dp_f[(i,(i-1)//2)]=max(dp_f[(i-1,(i-1)//2)], dp_t[(i-1,(i-1)//2)])
		dp_t[(i,(i-1)//2)]=dp_f[(i-1,(i-1)//2-1)]+a[i]
		dp_f[(i,(i-1)//2+1)]=max(dp_f[(i-1,(i-1)//2+1)], dp_t[(i-1,(i-1)//2+1)])
		dp_t[(i,(i-1)//2+1)]=dp_f[(i-1,(i-1)//2)]+a[i]
	print(max(dp_t[(n,n//2)],dp_f[(n,n//2)]))
if __name__ == '__main__':
	main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
minf=-10000000000000
x=[[0,0,0] for i in range(n)]
x[0]=[0,0,a[0]]
for i in range(n-1):
    if i%2==0:
        x[i+1]=[max(x[i][0],x[i][1]),x[i][2],x[i][0]+a[i+1]]
    else:
        x[i+1]=[max(x[i][1],x[i][2]),x[i][0]+a[i+1],x[i][1]+a[i+1]]
print(max(x[-1][1],x[-1][2]) if n%2==0 else max(x[-1][0],x[-1][1]))

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

pick_DP = [-float('INF')] * (n//2 + 2)
unpick_DP = [-float('INF')] * (n//2 + 2)
pick_DP[0] = 0
unpick_DP[0] = 0

for i, a in enumerate(A, 1):
    mini = (i-1)//2 - 1
    if mini <= 0:
        mini = 1
    maxi = (i+1)//2

    for num in range(maxi, mini-1, -1):
        if unpick_DP[num] < pick_DP[num]:
            unpick_DP[num] = pick_DP[num]
        pick_DP[num] = max(unpick_DP[num-1] + a, pick_DP[num])

print(max(pick_DP[n//2], unpick_DP[n//2]))

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

pick_DP = [-float('INF')] * n
unpick_DP = [-float('INF')] * n
pick_DP[0] = 0
unpick_DP[0] = 0

for i, a in enumerate(A, 1):
    mini = (i-1)//2 - 1
    if mini <= 0:
        mini = 1
    maxi = (i+1)//2

    temp = []
    for num in range(mini, maxi+1):
        temp.append(pick_DP[num])
        pick_DP[num] = max(unpick_DP[num-1] + a, pick_DP[num])

    for num, pre_pick in enumerate(temp, mini):
        if unpick_DP[num] < pre_pick:
            unpick_DP[num] = pre_pick

print(max(pick_DP[n//2], unpick_DP[n//2]))

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


if __name__ == '__main__':

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

    dp = [0] * N
    dp[1] = max(A[0], A[1])
    c = A[0]

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

    print(dp[-1])

Solution (Python):
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    odds = [0] * ((n + 1) // 2 + 1)
    for i, v in enumerate(a[::2]):
        odds[i+1] = odds[i] + v
    if n % 2 == 0:
        evens = [0] * (n // 2 + 1)
        for i, v in enumerate(a[1::2]):
            evens[i+1] = evens[i] + v
        ans = -float('inf')
        for i in range(n // 2 + 1):
            ans = max(ans, odds[i] + evens[-1] - evens[i])
        print(ans)
        return
    ans = odds[-1] - odds[1]
    dp = [float('inf')] * n
    dp[0] = a[0]
    dp[1] = a[1]
    ans = max(ans, max(a[:2]) + odds[-1] - odds[2])
    for i in range(2, n):
        if i % 2 == 0:
            dp[i] = dp[i-2] + a[i]
        else:
            dp[i] = max(dp[i-2], dp[i-3]) + a[i]
            ans = max(ans, max(dp[i-1], dp[i]) + odds[-1] - odds[i//2+2])
    print(ans)

main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
minf=-10000000000000
x=[[0,0,0] for i in range(n)]
x[0]=[0,0,a[0]]
for i in range(n-1):
    if i%2==0:
        x[i+1]=[max(x[i][0],x[i][1]),x[i][2],x[i][0]+a[i+1]]
    else:
        x[i+1]=[max(x[i][1],x[i][2]),x[i][0]+a[i+1],x[i][1]+a[i+1]]
print(max(x[-1][1],x[-1][2]) if n%2==0 else max(x[-1][0],x[-1][1]))

Solution (Python):
n = int(input())
nums = list(map(int,input().split()))
if n == 2:
    print(max(nums[0],nums[1]))
else:
    temp =[0]
    for i in range(n):
        if i%2 == 0:
            temp += [temp[-1]+nums[i]]
    dp = [[0,0,0] for _ in range(n)]
    dp[0][0] = nums[0]
    dp[1][0],dp[1][1],dp[1][2] = nums[1],nums[0],-float("inf")
    dp[2][0],dp[2][1],dp[2][2] = nums[2],nums[1],nums[0]
    for i in range(3,n):
        if i%2 == 0:
            dp[i][0] = max(dp[i-2]) + nums[i]
            dp[i][1] = max(dp[i-3]) + nums[i-1]
            dp[i][2] = temp[i//2]
        else:
            dp[i][0] = max(dp[i-2]) + nums[i]
            dp[i][1] = temp[(i-1)//2] + nums[i-1]
            dp[i][2] = -float("inf")
    print(max(dp[n-1]))

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

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

lacc = [0]*n
racc = [0]*n
lacc[0] = a[0]
lacc[1] = a[1]
racc[n-1] = a[n-1]
racc[n-2] = a[n-2]
for i in range(2,n):
    if i%2==0:
        lacc[i] = lacc[i-2]+a[i]
    else:
        lacc[i] = max(lacc[i-3],lacc[i-2])+a[i]
if n%2==0:
    print(max(lacc[n-2],lacc[n-1]))
    exit()
for i in range(n-3,-1,-1):
    if (n-1-i)%2==0:
        racc[i] = racc[i+2]+a[i]
    else:
        racc[i] = max(racc[i+3],racc[i+2])+a[i]
mx = max(racc[2],lacc[n-3])
for i in range(1,n-2):
    if i%2==0:
        mx = max(mx, max(lacc[i-2],lacc[i-1])+racc[i+2])
    else:
        mx = max(mx, max(racc[i+2],racc[i+3])+lacc[i-1])
print(mx)

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

main()

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 20
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    a = list(map(int,input().split()))
    if n%2 == 0:
        ans1 = 0
        ans2 = 0
        for i in range(n):
            if i%2 == 0:
                ans1 += a[i]
            else:
                ans2 += a[i]
        ans = max(ans1,ans2)

        cuml = [0] * (n + 1)
        cumr = [0] * (n + 1)

        for i in range(n):
            if i == 0:
                cuml[i + 1] = a[i]
            else:
                cuml[i + 1] = cuml[i - 1] + a[i]
        
        for i in range(n - 1,-1,-1):
            if i == n - 1:
                cumr[i] = a[i]
            else:
                cumr[i] = cumr[i + 2] + a[i]
        
        for i in range(1,n - 2,2):
                ans = max(ans,cuml[i] + cumr[i + 2])
    
    else:
        cuml = [0] * (n + 1)
        cumr = [0] * (n + 1)
        cumr2 = [0] * (n + 1)

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

        cumr.append(0)
        ans = -INF
        for i in range(n):
            ans = max(ans,cuml[i] + cumr[i + 2])
            if i <= n - 6 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr2[i + 2])
            if i <= n - 4 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr[i + 3])
    
    print(ans)

if __name__ =='__main__':
    main()

Solution (Python):
n,*a=map(int,open(0).read().split())
dp=[[0]*n for _ in range(3)]
for i in range(n):
	if i%2:
		dp[1][i]=max(dp[2][i-3]+a[i],dp[1][i-2]+a[i])
	elif i>1:
		dp[0][i]=max(dp[0][i-2]+a[i],dp[1][i-3]+a[i],dp[2][i-4]+a[i])
		dp[2][i]=dp[2][i-2]+a[i]
	else:
		dp[2][i]=dp[2][i-2]+a[i]
print(max(dp[2][-3],dp[1][-2],dp[0][-1]) if n%2 else max(dp[1][-1],dp[2][-2]))

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

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

INF = 10**18
limit = 4
S = (2*limit+3)
dpb = [-INF]*S
dpw = [-INF]*S
dpw[0] = 0
for i in range(N):
    a = A[i]
    dpb2 = [-INF]*S
    dpw2 = [-INF]*S
    for j in range(-limit, limit):
        if -limit <= j - 1 < limit:
            dpw2[j-1] = max(dpw2[j-1], dpb[j], dpw[j])
            dpb2[j-1] = max(dpb2[j-1], dpb[j], dpw[j])
        if -limit <= j + 1 < limit:
            dpb2[j+1] = max(dpb2[j+1], dpw[j]+a)
    dpw = dpw2[:]
    dpb = dpb2[:]

idx = N//2*2 - N
print(max(dpw[idx], dpb[idx]))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

dp0 = list2d(N+1, 4, -INF)
dp1 = list2d(N+1, 4, -INF)
dp0[0][2] = 0
for i, a in enumerate(A):
    for j in range(4):
        if j != 0:
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp0[i][j])
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp1[i][j])
        if j != 3:
            dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + a)
if N % 2 == 0:
    ans = max(dp0[N][2], dp1[N][2])
else:
    ans = max(dp0[N][1], dp1[N][1])
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

dp0 = list2d(N+1, 4, -INF)
dp1 = list2d(N+1, 4, -INF)
dp0[0][2] = 0
for i, a in enumerate(A):
    for j in range(4):
        if j != 0:
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp0[i][j])
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp1[i][j])
        if j != 3:
            dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + a)
if N % 2 == 0:
    ans = max(dp0[N][2], dp1[N][2])
else:
    ans = max(dp0[N][1], dp1[N][1])
print(ans)

Solution (Python):


import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()


dp0 = [defaultdict(lambda: -INF) for i in range(N+1)]

dp1 = [defaultdict(lambda: -INF) for i in range(N+1)]
dp0[0][0] = 0
for i, a in enumerate(A):
    for j in range(-2, 2):
        if j != -2:
            
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp0[i][j])
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp1[i][j])
        
        dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + a)

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

Solution (Python):

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

if n == 2 or n == 3:
    print(max(a_list))
elif n % 2 == 0: 
    dp = [[-float('inf') for _ in range(n)] for __ in range(2)]
    dp[1][-1] = a_list[-1]

    for j in reversed(range(2)):
        for i in reversed(range(n)):
            if j == 1 and i >= n-2:
                pass
            elif j == 1:
                dp[j][i] = dp[j][i+2] + a_list[i]
            elif i == n-2:
                dp[j][i] = dp[j+1][i+1]
            elif i > n-2:
                pass
            else:
                dp[j][i] = max(dp[j+1][i+1],dp[j][i+2] + a_list[i])
    print(dp[0][0])
else: 
    dp = [[-float('inf') for _ in range(n)] for __ in range(3)]
    dp[2][-1] = a_list[-1]

    for j in reversed(range(3)):
        for i in reversed(range(n)):
            if j == 2 and i >= n-2:
                pass
            elif j == 2:
                dp[j][i] = dp[j][i+2] + a_list[i]
            elif i == n-2:
                dp[j][i] = dp[j+1][i+1]
            elif i > n-2:
                pass
            else:
                dp[j][i] = max(dp[j+1][i+1],dp[j][i+2] + a_list[i])
    print(dp[0][0])

Solution (Python):
input()
aa = list(map(int, input().split()))
state = {(0,False)}
skipmax = len(aa)%2 + 1
state_all = {(i, True) for i in range(skipmax+1)}.union({(j, False) for j in range(skipmax+1)})
dp_0 = {a:None for a in state_all }
dp_0[(0,False)] = 0
skipcount = 0

def getmax(a, b):
    if a is None:
        return b
    if b is None:
        return a
    return max(a,b)

for i,a in enumerate(aa):
    dp_1 = {}
    for s in state_all:
        if s[1] & (dp_0[(s[0], False)] is not None):
            dp_1[s] = dp_0[(s[0], False)] + a
            continue
        dp_1[s] = getmax(dp_0[(s[0], True)], dp_0.get((s[0]-1, False), None))
    dp_0 = dp_1.copy()
if len(aa)%2:
    print(getmax(dp_0[(2,True)], dp_0[(1,False)]))
else:
    print(getmax(dp_0[(1,True)], dp_0[(0,False)]))

Solution (Python):
from collections import defaultdict

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

dp = defaultdict(lambda: -INF)
dp[(0, 0, 0)] = 0

for i, e in enumerate(a, 1):
    for j in range((i - 1) // 2, (i + 1) // 2 + 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)] + e

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

Solution (Python):
from sys import stdin, stdout
def main():
    N = int(stdin.readline())
    A = [0] + list(map(int, stdin.readline().rstrip().split()))
    dp = [0] * (N+1)
    prefix = [0] * (N+1)
    dp[1], prefix[1] = 0, A[1]
    for i in range(3, N, 2):
        prefix[i] = prefix[i-2]+A[i]
    for i in range(2, N+1):
        if i & 1:
            dp[i] = max(dp[i-1], A[i] + dp[i-2])
        else:
            dp[i] = max(dp[i-2] + A[i], prefix[i-1])
    
    stdout.write(str(dp[N])+"\n")
main()

Solution (Python):
import math

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

B = [{} for _ in range(N+1)]


for i in range(1,N+1):
  if i == 1:
    B[1][0] = 0
    B[1][1] = A[0]
  elif i == 2:
    B[2][1] = max(A[0],A[1])
    if N % 2 == 1:
      B[2][0] = 0
  else:
    if N % 2 == 0:
      for j in range(math.ceil((i-1)/2),(i+1)//2+1):
        m1 = B[i-2][j-1]+A[i-1] if j-1 in B[i-2] else -float('inf')
        m2 = B[i-1][j] if j in B[i-1] else -float('inf')
        B[i][j] = max(m1,m2)
    else:
      for j in range(math.ceil((i-2)/2),(i+1)//2+1):
        m1 = B[i-2][j-1]+A[i-1] if j-1 in B[i-2] else -float('inf')
        m2 = B[i-1][j] if j in B[i-1] else -float('inf')
        B[i][j] = max(m1,m2)
      

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

Solution (Python):
n = int(input())
a = [int(ai) for ai in input().split()]
if n % 2 == 0:
    s = [0,0]
    for i in range(n // 2):
        s = [max(s[q] for q in range(p+1)) + a[i*2+p] for p in range(2)]
    print(max(s))
else:
    s = [0,0,0]
    for i in range(n // 2):
        s = [max(s[q] for q in range(p+1)) + a[i*2+p] for p in range(3)]
    print(max(s))

Solution (Python):
n,*l=map(int,open(0).read().split())
p=[0,0]
d=p[:]
for l in l:d+=max(l+d[-2],[d,p][len(d)&1][-1]),;p+=l+p[-2],
print(d[-1])

Solution (Python):
n,*l=map(int,open(0).read().split())
p=[0,0]
d=[0,0]
i=0
for l in l:d+=max(l+d[-2],[d,p][i&1][-1]),;p+=l+p[-2],;i+=1
print(d[-1])

Solution (Python):
n,*l=map(int,open(0).read().split());p=[0]*n;d=p[:]
for i,l in enumerate(l):p[i]=l+p[i-2];d[i]=max(l+d[i-2],[d,p][i&1][i-1])
print(d[-1])