Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)

n = int(input())
a = list(map(int, input().split()))
# dp = [None]*(n+1)
#dp = [[None]*(n+1) for _ in range(2)]
dp = [[None]*(2) for _ in range(n+1)]

def solve(a):
    if len(a) == 0:
        return 0
    elif len(a) == 1:
        return a[0]
    elif len(a) == 2:
        v1 = a[0] + a[1]
        v2 = -a[0] - a[1]
        return max(v1, v2)

    v1 = a[0] + solve(a[1:])
    v2 = -a[0] + solve([-a[1]] + a[2:])
    return max(v1, v2)

def solve(a, flg):
    l = len(a)
    if dp[l][flg] is not None:
        return dp[l][flg]

    if flg == 1:
        a[0] = -a[0]

    if l == 0:
        dp[l][flg] = 0
    elif l == 1:
        dp[l][flg] = a[0]
    elif l == 2:
        v1 = a[0] + a[1]
        v2 = -a[0] - a[1]
        dp[l][flg] = max(v1, v2)
    else:
        v1 = a[0] + solve(a[1:], 0)
        v2 = -a[0] + solve(a[1:], 1)
        dp[l][flg] = max(v1, v2)
        # if flg == 0:
        #     v1 = a[0] + solve(a[1:], flg)
        #     v2 = -a[0] + solve(a[1:], abs(flg - 1))
        #     dp[l][flg] = max(v1, v2)
        # else:
        #     v1 = -a[0] + solve(a[1:], flg)
        #     v2 = a[0] + solve(a[1:], abs(flg - 1))
        #     dp[l][flg] = max(v1, v2)

    return dp[l][flg]

#def solve(idx):
print(solve(a, 0))
#print(solve(a, 1))
#print(solve(a, 0))
# v1 = solve(a, 1)
# v2 = solve(a, 0)
#
# print(v1, v2)
# print(max(v1, v2))


Fixed submission:
import sys
sys.setrecursionlimit(10**5)

n = int(input())
a = list(map(int, input().split()))
dp = [[None]*(2) for _ in range(n+1)]

dp[n-1][0] = a[n-1]
dp[n-1][1] = -a[n-1]

for i in reversed(range(n-1)):
    for j in range(2):
        #print('\n# i: ' + str(i))
        # Unexe
        unexe_unexe = a[i] + dp[i+1][0]
        exe_unexe = -a[i] + dp[i+1][1]
        dp[i][0] = max(unexe_unexe, exe_unexe)

        # Exe
        unexe_exe = a[i] + dp[i+1][1]
        exe_exe = -a[i] + dp[i+1][0]
        dp[i][1] = max(unexe_exe, exe_exe)

#print(dp)
#print(max(dp[0][0], dp[0][1]))
print(dp[0][0])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)

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

def solve(a):
    if len(a) == 0:
        return 0
    elif len(a) == 1:
        return a[0]
    elif len(a) == 2:
        v1 = a[0] + a[1]
        v2 = -a[0] - a[1]
        return max(v1, v2)

    v1 = a[0] + solve(a[1:])
    v2 = -a[0] + solve([-a[1]] + a[2:])
    return max(v1, v2)

# for i in range(n-1):
#     v1 = a[i] + a[i+1]
#     v2 = -a[i] - a[i+1]
#     if v2 > v1:
#         a[i] = -a[i]
#         a[i+1] = -a[i+1]

# print(a)
# print(sum(a))

print(solve(a))

Fixed submission:
import sys
sys.setrecursionlimit(10**5)

n = int(input())
a = list(map(int, input().split()))
dp = [[None]*(2) for _ in range(n+1)]

dp[n-1][0] = a[n-1]
dp[n-1][1] = -a[n-1]

for i in reversed(range(n-1)):
    for j in range(2):
        #print('\n# i: ' + str(i))
        # Unexe
        unexe_unexe = a[i] + dp[i+1][0]
        exe_unexe = -a[i] + dp[i+1][1]
        dp[i][0] = max(unexe_unexe, exe_unexe)

        # Exe
        unexe_exe = a[i] + dp[i+1][1]
        exe_exe = -a[i] + dp[i+1][0]
        dp[i][1] = max(unexe_exe, exe_exe)

#print(dp)
#print(max(dp[0][0], dp[0][1]))
print(dp[0][0])

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

def solve(a):
    if len(a) == 0:
        return 0
    elif len(a) == 1:
        return a[0]
    elif len(a) == 2:
        v1 = a[0] + a[1]
        v2 = -a[0] - a[1]
        return max(v1, v2)

    v1 = a[0] + solve(a[1:])
    v2 = -a[0] + solve([-a[1]] + a[2:])
    return max(v1, v2)

# for i in range(n-1):
#     v1 = a[i] + a[i+1]
#     v2 = -a[i] - a[i+1]
#     if v2 > v1:
#         a[i] = -a[i]
#         a[i+1] = -a[i+1]

# print(a)
# print(sum(a))

print(solve(a))

Fixed submission:
import sys
sys.setrecursionlimit(10**5)

n = int(input())
a = list(map(int, input().split()))
dp = [[None]*(2) for _ in range(n+1)]

dp[n-1][0] = a[n-1]
dp[n-1][1] = -a[n-1]

for i in reversed(range(n-1)):
    for j in range(2):
        #print('\n# i: ' + str(i))
        # Unexe
        unexe_unexe = a[i] + dp[i+1][0]
        exe_unexe = -a[i] + dp[i+1][1]
        dp[i][0] = max(unexe_unexe, exe_unexe)

        # Exe
        unexe_exe = a[i] + dp[i+1][1]
        exe_exe = -a[i] + dp[i+1][0]
        dp[i][1] = max(unexe_exe, exe_exe)

#print(dp)
#print(max(dp[0][0], dp[0][1]))
print(dp[0][0])