Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000)

class Solution():
    def dp(self, pos, sign):
        if pos == self.n-1:
            if sign == 0:
                return +self.lst[pos]
            else:
                return -self.lst[pos]
        elif (pos, sign) in self.vis:
            return self.rcd[pos][sign]
        elif sign == 0:
            self.rcd[pos][sign] = max(self.dp(pos+1, 0) + self.lst[pos], self.dp(pos+1, 1) - self.lst[pos])
            self.vis.add((pos, sign))
            return self.rcd[pos][sign]
        else:
            self.rcd[pos][sign] = max(self.dp(pos+1, 0) - self.lst[pos], self.dp(pos+1, 1) + self.lst[pos])
            self.vis.add((pos, sign))
            return self.rcd[pos][sign]

    def run(self):
        self.n = int(input())
        self.lst = list(map(int, raw_input().split()))
        self.rcd = [[0, 0] for _ in range(self.n)]
        self.vis = set()
        print(self.dp(0, 0))

solution = Solution()
solution.run()


Fixed submission:
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_d

N = int(input())
A = list(map(int, raw_input().split()))

ng_cnt = 0

for i in range(N):
    if A[i] < 0:
        ng_cnt += 1
        A[i] = -A[i]

if ng_cnt % 2 == 0:
    print '{}'.format( sum(A) )
else:
    print '{}'.format( sum(A) - min(A)*2)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)

class Solution():
    def dp(self, pos, sign):
        if pos == self.n-1:
            if sign == 0:
                return +self.lst[pos]
            else:
                return -self.lst[pos]
        elif (pos, sign) in self.vis:
            return self.rcd[pos][sign]
        elif sign == 0:
            self.rcd[pos][sign] = max(self.dp(pos+1, 0) + self.lst[pos], self.dp(pos+1, 1) - self.lst[pos])
            self.vis.add((pos, sign))
            return self.rcd[pos][sign]
        else:
            self.rcd[pos][sign] = max(self.dp(pos+1, 0) - self.lst[pos], self.dp(pos+1, 1) + self.lst[pos])
            self.vis.add((pos, sign))
            return self.rcd[pos][sign]

    def run(self):
        self.n = int(input())
        self.lst = list(map(int, raw_input().split()))
        self.rcd = [[0, 0] for _ in range(self.n)]
        self.vis = set()
        print(self.dp(0, 0))

solution = Solution()
solution.run()


Fixed submission:
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_d

N = int(input())
A = list(map(int, raw_input().split()))

ng_cnt = 0

for i in range(N):
    if A[i] < 0:
        ng_cnt += 1
        A[i] = -A[i]

if ng_cnt % 2 == 0:
    print '{}'.format( sum(A) )
else:
    print '{}'.format( sum(A) - min(A)*2)

Buggy python submission (verdict: Runtime Error):
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_

N = int(input())
A = list( map(int, raw_input().split()) )

rcd = [ [-1, -1] for _ in range(N) ]

def dp(pos, st):
    # terminal condition
    if pos == 0:
        if st == 0:
            return A[0]
        else:
            return -A[0]

    # if visit
    if rcd[pos][st] != -1:
        return rcd[pos][st]

    elif st == 0:
        # memorize
        rcd[pos][st] = max(dp(pos-1, 0) + A[pos], dp(pos-1, 1) + -A[pos])
        return rcd[pos][st]

    else: # st == 1
        # memorize
        rcd[pos][st] = max(dp(pos-1, 0) + -A[pos], dp(pos-1, 1) + A[pos])
        return rcd[pos][st]

print '{}'.format( max(dp(N-1, 0), dp(N-1, 1)) )


Fixed submission:
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_d

N = int(input())
A = list(map(int, raw_input().split()))

ng_cnt = 0

for i in range(N):
    if A[i] < 0:
        ng_cnt += 1
        A[i] = -A[i]

if ng_cnt % 2 == 0:
    print '{}'.format( sum(A) )
else:
    print '{}'.format( sum(A) - min(A)*2)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = map(int, raw_input().split())

def dp(A):
    if len(A) == 2:
        return A[0] + A[1] if A[0] + A[1] > -A[0] + -A[1] else -A[0] + -A[1]

    A_last, rA_last = A[-1], -A[-1]
    rA = A[:-1]
    rA[-1] = -rA[-1]
    return max( dp(A[:-1])+A_last, dp(rA)+rA_last)

print '{}'.format(dp(A))


Fixed submission:
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_d

N = int(input())
A = list(map(int, raw_input().split()))

ng_cnt = 0

for i in range(N):
    if A[i] < 0:
        ng_cnt += 1
        A[i] = -A[i]

if ng_cnt % 2 == 0:
    print '{}'.format( sum(A) )
else:
    print '{}'.format( sum(A) - min(A)*2)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = map(int, raw_input().split())

def dp(A):
    if len(A) == 2:
        return A[0] + A[1] if A[0] + A[1] > -A[0] + -A[1] else -A[0] + -A[1]
    A_last, rA_last = A[-1], -A[-1]
    A, rA = A[:-1], A[:-1]
    rA[-1] = -rA[-1]
    return max( dp(A)+A_last, dp(rA)+rA_last)


print '{}'.format(dp(A))


Fixed submission:
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_d

N = int(input())
A = list(map(int, raw_input().split()))

ng_cnt = 0

for i in range(N):
    if A[i] < 0:
        ng_cnt += 1
        A[i] = -A[i]

if ng_cnt % 2 == 0:
    print '{}'.format( sum(A) )
else:
    print '{}'.format( sum(A) - min(A)*2)