Reverse-Operation-D&C

def maxCrossingSum(arr, l, m, r):
    sm = 0
    left_sum = -float('inf')

    for i in range(m, l - 1, -1):
        sm = sm + arr[i]

        if (sm > left_sum):
            left_sum = sm

    sm = 0
    right_sum = -float('inf')
    for i in range(m, r + 1):
        sm = sm + arr[i]

        if (sm > right_sum):
            right_sum = sm

    return max(left_sum + right_sum - arr[m], left_sum, right_sum)


def maxSubArraySum(arr, l, r):
    if (l > r):
        return -float('inf')
    if (l == r):
        return arr[l]

    m = (l + r) // 2

    return max(maxSubArraySum(arr, l, m - 1),
               maxSubArraySum(arr, m + 1, r),
               maxCrossingSum(arr, l, m, r))


def reverse_operation(arr, n):
    b_1 = []
    for i in range(1, n, 2):
        b_1.append(arr[i] - arr[i - 1])
    b_2 = []
    for i in range(1, n - 1, 2):
        b_2.append(arr[i] - arr[i + 1])

    change = max(maxSubArraySum(b_1, 0, len(b_1) - 1), maxSubArraySum(b_2, 0, len(b_2) - 1))
    even_sum = 0
    for i in range(n):
        if i % 2 == 0:
            even_sum += arr[i]

    return even_sum + max(0, change)


def main():
    n = int(input())
    arr = list(map(int, input().split()))
    print(reverse_operation(arr, n))


if __name__ == "__main__":
    main()