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 = tuple(map(int, input().split()))

ms = [ [0 for i in range(3)] for j in range(n) ]

ms[0][0] = 0
ms[0][1] = 0
ms[0][2] = a[0]

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

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


print(ms[n - 1][1])

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

DP_odd = [0, A[0]]
DP_even = [0, max(A[0], A[1])]

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

if N % 2 == 1:
    ans = DP_odd[0]
else:
    ans = DP_even[1]

print(ans)

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

DP_odd = [0, 0, A[0]]
DP_even = [0, max(A[0], A[1])]

if N >= 3:
    DP_odd = [DP_even[0], max(DP_odd[1] + A[2], DP_even[1]), DP_odd[2] + A[2]]

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

if N % 2 == 1:
    ans = DP_odd[1]
else:
    ans = DP_even[1]

print(ans)

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def make4(initial, L, M, N, O):
    return [[[[initial for i in range(O)]
                for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def make3(initial, L, M, N):
    return [[[initial for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



def main():
    N = I()
    A = LI()
    dp_use = [-IINF] * 3
    dp_not_use = [-IINF] * 3
    dp_not_use[0] = 0

    for i in range(N):
        dp_use_next = [-IINF] * 3
        dp_not_use_next = [-IINF] * 3

        for j in range(3):
            if j - 1 >= 0:
                dp_not_use_next[j] = max(dp_use[j], dp_not_use[j-1])
            else:
                dp_not_use_next[j] = dp_use[j]
            dp_use_next[j] = dp_not_use[j] + A[i]

        
        
        dp_use = dp_use_next
        dp_not_use = dp_not_use_next

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


if __name__ == '__main__':
    main()

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


dp00 = -10**9
dp01 = 0
dp10 = -10**9
dp11 = 0

for i in range(n):
    if i % 2 == 0:
        dp10 = dp00 + a[i]
        dp00 = max(dp01, dp11)
        dp11 = dp01 + a[i]
    else:
        dp01 = dp11
        dp11 = dp00 + a[i]
        dp00 = max(dp00, dp10)
        if i == 3:
            dp10 = a[i]

if n % 2 == 0:
    print(max(dp01, dp11))
else:
    print(max(dp00, dp10))

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


dp00 = 0
dp01 = -10**15
dp10 = -10**15
dp11 = a[0]

for i in range(1, n):
    if i % 2 != 0:
        dp01 = dp11
        dp11 = dp00 + a[i]
        dp00 = max(dp00, dp10)
        if i == 3:
            dp10 = a[i]
    else:
        dp10 = dp00 + a[i]
        dp00 = max(dp01, dp11)
        dp11 = dp01 + a[i]

if n % 2 == 0:
    print(max(dp01, dp11))
else:
    print(max(dp00, dp10))

Solution (Python):
n=int(input())
arr=list(map(int,input().split()))
acum1=[0]
acum2=[0]
for i in range(n):
  if i%2==0:
    acum1.append(acum1[-1]+arr[i])
    acum2.append(acum2[-1]+0)
  else:
    acum1.append(acum1[-1]+0)
    acum2.append(acum2[-1]+arr[i])
if n%2==0:
  ans=max(acum1[n-1]-acum1[0],acum2[n]-acum2[1])
  for i in range(1,n+1,2):
    if i+3>n:
      continue
    tmp=(acum1[i]-acum1[0])+(acum2[n]-acum2[i+2])
    ans=max(ans,tmp)
else:
  ans=max(acum1[n-2]-acum1[0],acum2[n-1]-acum2[1],acum1[n]-acum1[2])
  for i in range(1,n+1,2):
    if i+3>n-1:
      continue
    tmp=(acum1[i]-acum1[0])+(acum2[n-1]-acum2[i+2])
    ans=max(ans,tmp)
  for i in range(2,n+1,2):
    if i+3>n:
      continue
    tmp=(acum2[i]-acum2[1])+(acum1[n]-acum1[i+2])
    ans=max(ans,tmp)
  for i in range(1,n+1,2):
    if i+4>n:
      continue
    tmp=(acum1[i]-acum1[0])+(acum1[n]-acum1[i+3])
    ans=max(ans,tmp)
  acummax=[-10**18]
  for i in range(1,n+1):
    if i+2>n:
      acummax.append(-10**18)
    else:
      if i%2==0:
        acummax.append(acum2[i]+acum1[n]-acum1[i+2])
      else:
        acummax.append(-10**18)
  for i in range(n-1,-1,-1):
    acummax[i]=max(acummax[i],acummax[i+1])
  for i in range(1,n+1,2):
    if i+6>n:
      continue
    tmp=(acum1[i]-acum1[0]-acum2[i+2])+acummax[i+3]
    ans=max(ans,tmp)
print(ans)

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

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

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

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

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

ans = 0

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

print(ans)

Solution (Python):
import sys

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

if N == 2:
    print(max(A))
    sys.exit()

dp = [0,max(A[:3]),A[0]+A[2]]
tmp1 = dp[:]
tmp2 = [0,max(A[:2]),0]
flag1 = False
flag2 = True if A[0] < A[2] and A[1] < A[2] else False
flag3 = False

for i in range(3,N):
    b = A[i]
    if i%2 == 0:
        dp[0] = max(tmp2[0],tmp1[0]+b)
        flag1 = True if tmp2[0] < tmp1[0]+b else False
        if flag3:
            dp[1] = max(tmp2[1],tmp1[1]+b)
            flag2 = True if tmp2[1] < tmp1[1]+b else False 
        else:
            dp[1] = max(tmp2[1],tmp2[0]+b,tmp1[1]+b)
            flag2 = True if tmp2[1] < tmp2[0]+b or tmp2[1] < tmp1[1]+b else False 
        dp[2] += A[i]
        tmp1 = dp[:]
    else:
        if flag1:
            dp[0] = max(tmp1[1],tmp2[0]+b)
            flag3 = True if tmp1[1] < tmp2[0]+b else False
        else:
            dp[0] = max(tmp1[1],tmp1[0]+b,tmp2[0]+b)
            flag3 = True if tmp1[1] < tmp1[0]+b or tmp1[1] < tmp2[0]+b else False
        if flag2:
            dp[1] = max(tmp1[2],tmp2[1]+b)
        else:
            dp[1] = max(tmp1[2],tmp1[1]+b,tmp2[1]+b)
        tmp2 = dp[:]
        
print (dp[1])

Solution (Python):
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
dp=[defaultdict(lambda:-float('inf'))for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])

Solution (Python):
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
dp=[defaultdict(lambda:-float('inf'))for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])

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

dp = [[0]*3]*N

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

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

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

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

if n==2:
    print(max(a[0],a[1]))
    exit()
    
dp=[[-float('inf'),-float('inf'),-float('inf')] for i in range(n)]



dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=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-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])

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

Solution (Python):
def find_max(a):
    n = len(a)

    if n <= 3:
        return max(a)

    dp = [[-(1 << 64)] * (2 + n % 2) for _ in range(n)]

    for i in range(2 + n % 2):
        dp[i][i] = a[i]
        dp[i + 1][i] = a[i]

    for i in range(2, n):
        for j in range(2 + n % 2):
            for extra_space in range(j + 1):
                curr_sum = dp[i - (2 + extra_space)][j - extra_space] + a[i]
                if curr_sum > dp[i][j]:
                    dp[i][j] = curr_sum

    return dp[-1][1 + n % 2]


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

    print(find_max(a))


main()

Solution (Python):
import pprint
N=int(input())
A=list(map(int,input().split()))
if N%2==0:
    dp=[[-float("inf") for _ in range(2)] for _ in range(N+10)]
    if N==2:
        print(max(A[0],A[1]))
    else:
        for i in range(N):
            if i==0:            
                dp[0][0]=A[0]
            elif i==1:          
                dp[1][1]=A[1]
            elif i==2:          
                dp[2][0]=A[0]+A[2]
            else:                   
                for j in range(2):
                    if j==0:                                                    
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])                  
                    elif j==1:                                                  
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])  
        print(max(dp[N-1][1],dp[N-2][0]))                                       
else:
    
    dp=[[-float("inf") for _ in range(3)] for _ in range(N+10)]
    if N==3:
        print(max(A[0],A[1],A[2]))
    else:
        for i in range(N):
            if i<4:
                if i==0:                                        
                    dp[0][0]=A[0]
                if i==1:                                        
                    dp[1][1]=A[1]
                if i==2:                                        
                    dp[2][2]=A[2]
                    dp[2][0]=A[0]+A[2]
                if i==3:                                        
                    dp[3][1]=max(dp[1][1]+A[3],dp[0][0]+A[3])
            else:                                                                               
                for j in range(3):
                    if j==0:                                                                    
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])                                  
                    elif j==1:                                                                  
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])                  
                    else:                                                                       
                        dp[i][2]=max(dp[i][2],dp[i-2][2]+A[i],dp[i-3][1]+A[i],dp[i-4][0]+A[i])  
        print(max(dp[N-1][2],dp[N-2][1],dp[N-3][0]))

Solution (Python):
def f_select_half():
    
    from collections import defaultdict
    N = int(input())
    A = [int(i) for i in input().split()]

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

    for k, a in enumerate(A, 1):
        j = k // 2
        for x in range(j - 1, j + 2):
            dp[(k, x, 0)] = max(dp[(k - 1, x, 0)], dp[k - 1, x, 1])
            
            dp[(k, x, 1)] = dp[(k - 1, x - 1, 0)] + a
    return max(dp[(N, N // 2, f)] for f in (0, 1))

print(f_select_half())

Solution (Python):
def get_next_unchosen(current , chooseNum):
    if (chooseNum , 0) in current or (chooseNum , 1) in current:
        if (chooseNum , 0) in current and (chooseNum ,1) in current:
            return max(current[(chooseNum, 0)] , current[(chooseNum, 1)])
        if (chooseNum , 0) in current:
            return current[(chooseNum , 0)]
        return current[(chooseNum,1)]
    return None


def calc_next_state(current, must_choose_num, a):
    next = {}
    current_unchosen_nums = [choose_num  for (choose_num, prev_chosen) in current.keys() if prev_chosen == 0 and choose_num >= must_choose_num - 1]
    for chooseNum in current_unchosen_nums:
        next[(chooseNum + 1, 1)] = current[(chooseNum , 0)] + a
    for chooseNum in range(must_choose_num, N):
        n = get_next_unchosen(current, chooseNum)
        if n is None:
            break
        else:
            next[(chooseNum , 0)] = n
    return next


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

totalChooseNum = N // 2
dp = {(0, 0) : 0}
for i in range(0, N):
    ai = A[i]
    canChooseNum = (N - i + 1) // 2
    mustChooseNum = max(totalChooseNum - canChooseNum, 0)
    dp = calc_next_state(dp, mustChooseNum, ai)

result = max(dp[(totalChooseNum, 0)] , dp[(totalChooseNum , 1)])
print(result)

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

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
m=n//2
t=n%2+2
dp=[0]*t
for i in range(m):
    for j in range(t):
        dp[j]+=l[2*i+j]
    for j in range(1,t):
        dp[j]=max(dp[j],dp[j-1])
print(dp[-1])

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

Solution (Python):
C = -(10**15 + 7)


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[i, 0] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[i-1, 1], A[i-1])
    for i in range(2, N+1):
        for j in range(i//2-1, (i+1)//2 + 1):
            if j < 0:
                continue
            
            dp[i, j] = max(dp[i, j], dp[i-2, j-1] + A[i-1],
                           dp[i-3, j-1] + A[i-1], dp[i-4, j-1] + A[i-1])
    print(max(dp[N, K], dp[N-1, K], dp[N-2, K]))
    
    
    
    


if __name__ == '__main__':
    main()

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


a1=[]
a2=[]

for i in range(n):
    if i%2==0:
        a1.append(a[i])
    else:
        a2.append(a[i])


a3=list(itertools.accumulate(a1))
a4=list(itertools.accumulate(a2))


x1=sum(a1)
x2=sum(a2)


if n%2==0:
    ans=-float('inf')
    for i in range(n//2):
        ans=max(a3[i]+x2-a4[i],ans)
    print(max(ans,x1,x2))
else:
    
    ans1=sum(a1)-min(a1)
    
    dp1 = [-float('inf')] * (n // 2 + 1)
    dp1[0] = a1[0]
    
    dp2 = [-float('inf')] * (n // 2)
    dp2[0] = a2[0]
    for i in range(n // 2 - 1):
        dp2[i + 1] = max(a3[i] + a2[i + 1], dp2[i] + a2[i + 1])
        if i==0:
            dp1[i + 2] = dp2[i] + a1[i + 2]
        else:
            dp1[i + 2] = max(dp2[i] + a1[i + 2], dp1[i + 1] + a1[i + 2])
    print(max(dp1[-1], dp2[-1],ans1))

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
DIM, PER = 0, 1
MIN, MAJ = 0, 1


dp = [[None, None] for _ in range(n)]
dp[0] = [0, a[0]]
dp[1] = [0, max(a[0], a[1])]
for i in range(2, n):
    if i % 2 == 0:
        dp[i][MIN] = max(dp[i - 2][MIN] + a[i], dp[i - 1][PER])
        dp[i][MAJ] = dp[i - 2][MAJ] + a[i]
    else:
        dp[i][DIM] = max(dp[i - 2][DIM] + a[i], dp[i - 1][MIN])
        dp[i][PER] = max(dp[i - 2][PER] + a[i], dp[i - 1][MAJ])
if n % 2 == 0:
    print(dp[n - 1][PER])
else:
    print(dp[n - 1][MIN])

Solution (Python):


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

select_num = N//2
inf = -10e+100

Dp_f = [[inf] * (3) for _ in range(N+1)]
Dp_s = [[inf] * (3) for _ in range(N+1)]


pre_margin = 0
for i in range(1,N+1):
    Start = (i-1)//2
    End = (i+1)//2
    
    cur_margin = Start
    
    for j in range(Start,End+1):
        Dp_f[i][j-cur_margin] = max(Dp_s[i-1][j-pre_margin], Dp_f[i-1][j-pre_margin])   
        
        
    for j in range(Start,End+1):
        if j-1 == 0:
            Dp_s[i][j-cur_margin] = 0 + A[i]
        else:
            Dp_s[i][j-cur_margin] = Dp_f[i-1][j-1-pre_margin]+A[i]
    
    pre_margin = cur_margin
print(max(Dp_f[-1][select_num - cur_margin], Dp_s[-1][select_num - cur_margin]))

Solution (Python):
N=int(input())
A=list(map(int, input().split()))
if N==2:
  print(max(A))
  exit() 
  
dp=[[0,0,0] 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>1:
    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]
  if i>3 :
    dp[i][2]=max(dp[i-4][0],dp[i-3][1],dp[i-2][2])+A[i]
if N%2==1:
  ans=max(dp[-1][2],dp[-2][1],dp[-3][0])
else:
  ans=max(dp[-1][1],dp[-2][0])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
if n <= 3:
  print(max(a))
  exit()

a = tuple(a)
dp = [[-10**15]*3 for i in range(n)]

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

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def make4(initial, L, M, N, O):
    return [[[[initial for i in range(O)]
                for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def make3(initial, L, M, N):
    return [[[initial for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



def main():
    N = I()
    A = LI()
    dp_use = [-IINF] * 5
    dp_not_use = [-IINF] * 5
    dp_not_use[0] = 0

    for k in range(N):
        dp_use_next = [-IINF] * 5
        dp_not_use_next = [-IINF] * 5
        for current_dif in range(-3,2):
            if current_dif-1 >= -3:
                dp_use_next[current_dif] = dp_not_use[current_dif - 1] + A[k]
            if current_dif+1 < 2:
                dp_not_use_next[current_dif] = max(dp_use[current_dif+1], dp_not_use[current_dif+1])
        dp_use = dp_use_next
        dp_not_use = dp_not_use_next

    dif = N//2 - (N-N//2)
    print(max(dp_use[dif], dp_not_use[dif]))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
INF = 10**18
dp_use = [-INF] * 5
dp_not_use = [-INF] * 5
dp_not_use[0] = 0
 
for a in A:
    tmp_use = [-INF] * 5
    tmp_not_use = [-INF] * 5
    for current_dif in range(-3,2):
        if current_dif-1 >= -3:
            tmp_use[current_dif] = dp_not_use[current_dif - 1] + a
        if current_dif+1 < 2:
            tmp_not_use[current_dif] = max(dp_use[current_dif+1], dp_not_use[current_dif+1])
    dp_use = tmp_use
    dp_not_use = tmp_not_use
dif = n//2 - (n-n//2)
print(max(dp_use[dif], dp_not_use[dif]))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
if n == 3:
    print(max(a))
    quit()
dp1 = [-inf]*(n+1) 
dp2 = [-inf]*(n+1)
dp3 = [-inf]*(n+1)
dp1[0] = 0
dp2[0] = 0
dp3[0] = 0
dp1[1] = a[0]
dp2[2] = a[1]
for i in range(3,n+1):
    dp1[i] = dp1[i-2] + a[i-1]
    dp2[i] = max(dp2[i-2],dp1[i-3]) + a[i-1]
    dp3[i] = max(dp3[i-2],dp2[i-3],dp1[i-4]) + a[i-1]
if n % 2:
    print(max(dp1[n-2], dp2[n], dp3[n]))
else:
    print(max(dp1[n-1], dp2[n]))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
if n == 3:
    print(max(a))
    quit()
dp1 = [-inf]*(n+1) 
dp2 = [-inf]*(n+1)
dp3 = [-inf]*(n+1)
dp1[0] = 0
dp2[0] = 0
dp3[0] = 0
dp1[1] = a[0]
dp2[2] = a[1]
for i in range(3,n+1):
    dp1[i] = dp1[i-2] + a[i-1]
    dp2[i] = max(dp2[i-2],dp1[i-3]) + a[i-1]
    dp3[i] = max(dp3[i-2],dp2[i-3],dp1[i-4]) + a[i-1]
if n % 2:
    print(max(dp1[n-2], dp2[n], dp3[n]))
else:
    print(max(dp1[n-1],dp2[n]))

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

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

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

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

Solution (Python):
import numpy as np
n = int(input())
a = list(map(int,input().split()))

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

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]


    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

        
    co = 0

    for i in range(0,n,2):
        if i + 2 <= n-1:
            ans = max(ans,co+l1[i+1],co+po[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)