2178C - First or Second

we can iterate the fixed positon , the items after that fixed item can only contribute -1 * a[i] and for the items before that, two cases rise as:

a) the first item a[0] < 0:

eg> -A B -C -D E .... we can get the greedy sum: B+C+D+E-A cause negative items can be select as 'Second' first, but a[0] must be pick as 'First'.

b) the first item a[0] >= 0:

eg> A B -C -D E .... we can get the greedy sum: B+C+D+E+A cause negative items can be select as 'Second' first.

import sys

if __name__ == "__main__":
    all_cases = sys.stdin.readline()
    all_cases = int(all_cases)

    for i in range(all_cases):
        N = int(input())

        an = [int(x) for x in sys.stdin.readline().split(" ")]
        sumn = [0] * (N + 1)
        psumn = [0] * (N + 1)
        for i in range(0, N):
            sumn[i + 1] = an[i] + sumn[i]
            psumn[i + 1] = abs(an[i]) + psumn[i]

        # print("sumn = ", sumn)

        ans = -1e9
        for i in range(1, N + 1):
            if i - 1 == 0:
                positive_part = 0
            else:
                if an[0] >= 0:
                    positive_part = psumn[i - 1]
                else:
                    positive_part = psumn[i - 1] + 2 * an[0]
            neg_part = -1 * (sumn[N] - sumn[i])
            ans = max(ans, positive_part + neg_part)
        print(ans)