Maximum Sum on Even Positions (Codeforces 1373D)
Tags: Greedy, divide and conquer

You are given an array $$$a$$$ consisting of $$$n$$$ integers. Indices of the array start from zero (i. e. the first element is $$$a_0$$$, the second one is $$$a_1$$$, and so on).You can reverse at most one subarray (continuous subsegment) of this array. Recall that the subarray of $$$a$$$ with borders $$$l$$$ and $$$r$$$ is $$$a[l; r] = a_l, a_{l + 1}, \dots, a_{r}$$$.Your task is to reverse such a subarray that the sum of elements on even positions of the resulting array is maximized (i. e. the sum of elements $$$a_0, a_2, \dots, a_{2k}$$$ for integer $$$k = \lfloor\frac{n-1}{2}\rfloor$$$ should be maximum possible).You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$a$$$. The second line of the test case contains $$$n$$$ integers $$$a_0, a_1, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output: For each test case, print the answer on the separate line — the maximum possible sum of elements on even positions after reversing at most one subarray (continuous subsegment) of $$$a$$$.


Sample Inputs:
4
8
1 7 3 4 7 6 2 9
5
1 2 1 2 1
10
7 8 4 5 7 6 8 9 7 3
4
3 1 2 1

Sample Outputs:
26
5
37
5

Solution (Python):
def main():
    cases_array = []
    size_cases = []
    number_cases = int(input())
    for _ in range(number_cases):
        size_cases.append(int(input()))
        cases_array.append([int(value) for value in input().split(' ')])
    for (id, case) in enumerate(cases_array):
        difference_even_odd_before = []
        difference_even_odd_after = []
        sum_even = 0
        for idx in range(0, size_cases[id], 2):
            sum_even += case[idx]
            if idx > 0:
                difference_even_odd_before.append(case[idx - 1] - case[idx])
            if idx + 1 < size_cases[id]:
                difference_even_odd_after.append(case[idx + 1] - case[idx])
        max_sum_partial_deob = 0
        max_sum_so_far_deob = 0
        for value in difference_even_odd_before:
            max_sum_partial_deob = max_sum_partial_deob + value
            max_sum_partial_deob = max(max_sum_partial_deob, value)
            max_sum_so_far_deob = max(max_sum_partial_deob, max_sum_so_far_deob)
        max_sum_partial_deoa = 0
        max_sum_so_far_deoa = 0
        for value in difference_even_odd_after:
            max_sum_partial_deoa = max_sum_partial_deoa + value
            max_sum_partial_deoa = max(max_sum_partial_deoa, value)
            max_sum_so_far_deoa = max(max_sum_partial_deoa, max_sum_so_far_deoa)
        max_between = max(max_sum_so_far_deob, max_sum_so_far_deoa)
        if max_between <= 0:
            max_between = 0
        print(max_between + sum_even)
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    cases_array = []
    size_cases = []
    number_cases = int(input())
    for _ in range(number_cases):
        size_cases.append(int(input()))
        cases_array.append([int(value) for value in input().split(' ')])
    for (id, case) in enumerate(cases_array):
        difference_even_odd_before = []
        difference_even_odd_after = []
        sum_even = 0
        for idx in range(0, size_cases[id], 2):
            sum_even += case[idx]
            if idx > 0:
                difference_even_odd_before.append(case[idx - 1] - case[idx])
            if idx + 1 < size_cases[id]:
                difference_even_odd_after.append(case[idx + 1] - case[idx])
        max_sum_partial_deob = 0
        max_sum_so_far_deob = 0
        for value in difference_even_odd_before:
            max_sum_partial_deob = max_sum_partial_deob + value
            max_sum_partial_deob = max(max_sum_partial_deob, value)
            max_sum_so_far_deob = max(max_sum_partial_deob, max_sum_so_far_deob)
        max_sum_partial_deoa = 0
        max_sum_so_far_deoa = 0
        for value in difference_even_odd_after:
            max_sum_partial_deoa = max_sum_partial_deoa + value
            max_sum_partial_deoa = max(max_sum_partial_deoa, value)
            max_sum_so_far_deoa = max(max_sum_partial_deoa, max_sum_so_far_deoa)
        max_between = max(max_sum_so_far_deob, max_sum_so_far_deoa)
        if max_between <= 0:
            max_between = 0
        print(max_between + sum_even)
if __name__ == '__main__':
    main()

Solution (Python):
from __future__ import division, print_function
import os, sys, time
from io import BytesIO, IOBase
ONLINE_JUDGE = 1
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
start_time = time.time()

def maiorLucro(arr):
    maior = soma = 0
    for x in arr:
        soma += x
        if soma < 0:
            soma = 0
        if soma > maior:
            maior = soma
    return maior

def solve():
    i()
    num = il()
    prefImp = [j - i for (i, j) in zip(num[0::2], num[1::2])]
    prefPar = [i - j for (i, j) in zip(num[1::2], num[2::2])]
    maxImp = maiorLucro(prefImp)
    maxPar = maiorLucro(prefPar)
    adicional = max(maxImp, maxPar)
    print(sum(num[::2]) + (adicional if adicional > 0 else 0))

def main():
    t = ii()
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print('Tempo :', time.time() - start_time, ' segundos')
        sys.stdout.close()
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
i = input

def ii():
    return int(input())

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

def isr():
    return input().strip()

def im():
    return map(int, input().split())
if __name__ == '__main__':
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open('input.txt', 'r')
        sys.stdout = open('output.txt', 'w')
    main()