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

Solution (Python):
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())
A = lmi()



def solve2():
    """

6
1 2 3 4 5 6
>> 12
6
2 1 3 4 5 6
>> 12
    :return:
    """
    assert N % 2 == 0
    even = [0]
    odd = [0]
    for v in range(N):
        if v % 2 == 0:
            even.append(even[-1] + A[v])
        else:
            odd.append(odd[-1] + A[v])

    
    
    ans = 0
    for i in range(len(even)):
        ans = max(ans, even[i] + odd[-1] - odd[i])
    print(ans)


def solve():
    
    dp = [[-INF] * 3 for _ in range(N // 2 + 1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0

    for v in range(N):
        for ignore_count in range(3):
            if ignore_count == 0:
                flag = (v < N - 1 and v % 2 == 0)
                dp_slice = v // 2
            elif ignore_count == 1:
                flag = (v % 2 == 1)
                dp_slice = v // 2
            else:  
                flag = (v > 1 and v % 2 == 0)
                dp_slice = v // 2 - 1
            if flag:
                dp[dp_slice + 1][ignore_count] = max(dp[dp_slice][ignore_count] + A[v], dp[dp_slice + 1][ignore_count])
                if ignore_count != 2:
                    dp[dp_slice + 1][ignore_count + 1] = max(dp[dp_slice + 1][ignore_count],
                                                             dp[dp_slice + 1][ignore_count + 1])
                
                
                

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


if N % 2 == 1:
    solve()
else:
    solve()

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
a = nl()
dp = [[0]*3 for _ in range(n+5)]
t = n%2
for i in range(n):
    dp[i][0] = dp[i-2][0] + a[i]
    dp[i][1] = max(dp[i-2][1], dp[i-3][0]) + a[i]
    if t:
        dp[i][2] = max(dp[i-2][2], dp[i-3][1], dp[i-4][0]) + a[i]
if t:
    print(max(dp[n-3][0], dp[n-2][1], dp[n-1][2]))
else:
    print(max(dp[n-2][0], dp[n-1][1]))

Solution (Python):
n = int(input())
a = [int(num) for num 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 == 1:
        dp[i+1][2] = max(dp[i][2],dp[i][1],dp[i][0]) + a[i*2+2]

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

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

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

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

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

print(dp[-1])

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

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):
from collections import *
import sys
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()
if N%2 == 0:
    v1 = sum(A[::2])
    v2 = sum(A[1::2])
    M = max(v1, v2)
    l = 0
    for i in range(0, N, 2):
        v2 -= A[i+1]
        l += A[i]
        M = max(l + v2, M)
    print(M)
else:
    INF = 10**18
    DP = [[[-INF]*N for _ in range(3)] for _ in range(2)]
    DP[1][0][0] = A[0]
    DP[0][1][0] = 0
    for i in range(1, N):
        DP[1][0][i] = A[i] + DP[0][0][i-1]
        DP[1][1][i] = A[i] + DP[0][1][i-1]
        DP[1][2][i] = A[i] + DP[0][2][i-1]
        DP[0][0][i] = DP[1][0][i-1]
        DP[0][1][i] = max(DP[0][0][i-1], DP[1][1][i-1])
        DP[0][2][i] = max(DP[0][1][i-1], DP[1][2][i-1])

    print(max(DP[0][1][N-1], DP[1][1][N-1], DP[1][2][N-1]))

Solution (Python):


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

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

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

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

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

INF = 10 ** 17

start = []
start.append((0, l[0]))
start.append((0,max(l[0],l[1])))

for i in range(2, N):
    if i % 2 == 0:
        left = [start[-1][1], start[-2][0] + l[i]]
        right = [start[-2][1] + l[i]]
    else:
        left = [start[-1][0], start[-2][0] + l[i]]
        right = [start[-1][1], start[-2][1] + l[i]]
    start.append((max(left),max(right)))

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

Solution (Python):
import sys
n = int(input())
a = list(map(int, input().split()))
if n%2 == 0:
	dp = [[-10**20 for _ in range(2)] for _ in range(n)]
	dp[0][0] = a[0]
	dp[0][1] = 0
	dp[1][1] = a[1]
	for i in range(1, n):
		if i%2 == 0:
			dp[i][0] = dp[i-2][0] + a[i]
			dp[i][1] = max(dp[i-1][0], dp[i-1][1])
		else:
			dp[i][0] = dp[i-1][0]
			if i > 1:
				dp[i][1] = max(dp[i-2][1] + a[i], dp[i-3][0] + a[i])

else:
	dp = [[-10**20 for _ in range(3)] for _ in range(n)]
	dp[0][0] = a[0]
	dp[0][1] = 0
	dp[1][1] = a[1]
	dp[0][2] = 0
	dp[1][2] = 0
	dp[2][2] = a[2]

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

print(max(dp[n-1]))

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()
a = na()

if n % 2 == 0:
    pre = [0]
    for i in range(0, n, 2):
        pre.append(pre[-1] + a[i])
    suf = [0]
    b = a[::-1]
    for i in range(0, n, 2):
        suf.append(suf[-1] + b[i])
    ans = -99999999999999999
    for i in range(len(pre)):
        ans = max(ans, pre[i] + suf[-1-i])
    print(ans)
else:
    pre = [0]
    for i in range(0, n, 2):
        pre.append(pre[-1] + a[i])
    
    
    
    ans = -999999999999999999
    mx = 0
    for i in range(1, n, 2):
        ans = max(ans, mx + pre[-1] - pre[i//2+1])
        mx = max(mx + a[i], pre[i//2+1])
    ans = max(ans, mx)
    print(ans)

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)]))