Buggy python submission (verdict: Time Limit Exceeded):
import sys, math
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))
    """
    dp[i][j] = (1からi番目の数のうちどの２個も連続しないようにj個選んだ時の和の最大)
    と置くらしい。何故その発想になるんだ？？
    最初は左右で分けて尺取りみたいなことをすれば行けると思ったが、左右の分け目を１つずらしたら
    最適解がガラッと変わって困った　→　じゃあDP、って感じなのかなあ

    このままだとO(N^2)なので状態数を減らす。
    １．j個は連続しないようにとるので、j <= (1 + i) // 2は確定。(iは1-indexedなことに注意)
    ２．残った(N - i)から連続しないように(N // 2 - j)個選ぶには、(N // 2 - j) <= (1 + N - i) // 2、
    　　すなわち(i - 3) // 2 <= jが必要。
    　　（j = 0,1,とか考えてもいいが、最終的にdp[N][N // 2]を求めるのにこれらは寄与しない）
    以上より、(i - 3) // 2 <= j <= (i + 1) // 2の範囲のみでdpすれば十分。

    肝心の遷移だが、A = [3, 1, 4, 1, 5, 9, 2]を例にとると
            i\j|  0  1  2   3   4       dp[5][1] = max(A[5], dp[4][1])
            ----------------------      dp[5][2] = max(A[5] + dp[3][1], dp[4][2])
              1|  0  3                  dp[5][3] = A[5] + dp[3][2]
              2|  0  3
              3|  0  4  7               dp[6][2] = max(A[6] + dp[4][1], dp[5][2])
              4|     4  7               dp[6][3] = max(A[6] + dp[4][2], dp[5][3])
              5|     5  9  12
              6|        9  12           のように、最後の数をとるか取らないかで場合分けすればよい。
              7|        9  12  14       ただしiが奇数の場合、dp[i][(i + 1) // 2]は必ずA[i]を
                                        加えざるを得ないため場合分けは起きないことに注意。
    """

    dp = [[0] * (N // 2 + 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 == 0:
            dp[i][i // 2 - 1] = max(A[i] + dp[i - 2][i // 2 - 1], dp[i - 1][i // 2 - 1])
            dp[i][i // 2] = max(A[i] + dp[i - 2][i // 2 - 1], dp[i - 1][i // 2])
        elif i > 3:
            dp[i][(i - 3) // 2] = max(A[i] + dp[i - 2][(i - 5) // 2], dp[i - 1][(i - 3) // 2])
            dp[i][(i - 1) // 2] = max(A[i] + dp[i - 2][(i - 3) // 2], dp[i - 1][(i - 1) // 2])
            dp[i][(i + 1) // 2] = A[i] + dp[i - 2][(i - 1) // 2]
        else:
            dp[3][1] = max(A[1:4])
            dp[3][2] = A[1] + A[3]
    print(dp[N][N // 2])


if __name__ == "__main__":
    main()


Fixed submission:
import sys, math
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))
    """
    dp[i][j] = (1からi番目の数のうちどの２個も連続しないようにj個選んだ時の和の最大)
    と置くらしい。何故その発想になるんだ？？
    最初は左右で分けて尺取りみたいなことをすれば行けると思ったが、左右の分け目を１つずらしたら
    最適解がガラッと変わって困った　→　じゃあDP、って感じなのかなあ

    このままだとO(N^2)なので状態数を減らす。
    １．j個は連続しないようにとるので、j <= (1 + i) // 2は確定。(iは1-indexedなことに注意)
    ２．残った(N - i)から連続しないように(N // 2 - j)個選ぶには、(N // 2 - j) <= (1 + N - i) // 2、
    　　すなわち(i - 3) // 2 <= jが必要。
    　　（j = 0,1,とか考えてもいいが、最終的にdp[N][N // 2]を求めるのにこれらは寄与しない）
    以上より、(i - 3) // 2 <= j <= (i + 1) // 2の範囲のみでdpすれば十分。

    肝心の遷移だが、A = [3, 1, 4, 1, 5, 9, 2]を例にとると
            i\j|  0  1  2   3   4       dp[5][1] = max(A[5], dp[4][1])
            ----------------------      dp[5][2] = max(A[5] + dp[3][1], dp[4][2])
              1|  0  3                  dp[5][3] = A[5] + dp[3][2]
              2|  0  3
              3|  0  4  7               dp[6][2] = max(A[6] + dp[4][1], dp[5][2])
              4|     4  7               dp[6][3] = max(A[6] + dp[4][2], dp[5][3])
              5|     5  9  12
              6|        9  12           のように、最後の数をとるか取らないかで場合分けすればよい。
              7|        9  12  14       ただしiが奇数の場合、dp[i][(i + 1) // 2]は必ずA[i]を
                                        加えざるを得ないため場合分けは起きないことに注意。
    """

    # iの偶奇でdp[i]をeven, oddに分割してメモリ削減
    odd = [0, A[1], 0]
    even = [0, max(A[1], A[2])]
    for i in range(3, N + 1):
        if i % 2 == 0:
            even[0] = max(A[i] + even[0], odd[1])
            even[1] = max(A[i] + even[1], odd[2])
        elif i > 3:
            odd[0] = max(A[i] + odd[0], even[0])
            odd[1] = max(A[i] + odd[1], even[1])
            odd[2] = A[i] + odd[2]
        else:
            odd[1] = max(A[1:4])
            odd[2] = A[1] + A[3]
    if N % 2 == 0:
        print(even[1])
    else:
        print(odd[1])


if __name__ == "__main__":
    main()