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



Sample input:
6
1 2 3 4 5 6


Sample output:
12

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))

if n//2==n/2:
    m=sum(l[::2])
    mx=m
    for i in range(0,n,2):
        m=m+l[n-i-1]-l[n-i-2]
        mx=max(m,m-(l[n-i-1]-l[n-i-2]))
print(mx)

Submission status: Runtime Error

Solution code:


def main():
    N = int(input())
    N2 = N//2
    A = [int(x) for x in input().split()]

    if N==2:
        print(max(A))
        return

    from functools import lru_cache
    @lru_cache(None)
    def dp(i, k):
        if i >= N:
            return float("-inf")
        if i+2*(k-1) >= N:
            return float("-inf")
        if k==1:
            if i < N:
                return A[i]
            else:
                return float("-inf")

        use = A[i] + max(dp(i+2,k-1), dp(i+3,k-1), dp(i+4, k-1))
        nouse = dp(i+1,k)
        return max(use, nouse)

    ans = dp(0, N//2)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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()


# dp = [[-INF]*3 for _ in range(N)]
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])

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


def solve():
    # dp[N][ignored]
    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:  # ignore_count == 2:
                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 ignore_count==0:
                #     dp[dp_slice + 1][2] = max(dp[dp_slice + 1][ignore_count],
                #                                              dp[dp_slice + 1][2])


                # if ignore_count:
                #     dp[dp_slice + 1][ignore_count] = dp[dp_slice][ignore_count - 1]

    print(max(dp[-1]))


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

Submission status: Runtime Error

Solution code:
N = input(int())
A = list(map(int,input().split()))
A_1 = [A[i] for i in range(A) if i%2!=0] 
A_2 = [A[i] for i in range(A) if i%2==0] 

ans = 0

if N%2==0:
  sum_A_1=sum(A_1)
  sum_A_2=sum(A_2)
else:
  sum_A_1=sum(A_1)-min(A_1)
  sum_A_2=sum(A_2)-min(A_2)
  
if sum_A_1>=sum_A_2:
  ans = sum_A_1
else:
  ans = sum_A_2

print(ans)