1A2014

#include <stdio.h>

// Złożoność czasowa O(n)
// Złożoność pamięciowa O(n)

int maxdiff(int A[], int n)
{
    int pre[n]; // Tablica sum prefiksowych
    pre[0] = A[0];
    for (int i = 1; i < n; i++)
        pre[i] = A[i] + pre[i-1];

    int suf[n]; // Tablica sum sufiksowych
    suf[n - 1] = A[n - 1];
    for (int i = n - 2; i >= 0; i--)
        suf[i] = suf[i + 1] + A[i];

    for (int i = 1; i < n; i++) // pre[i] = maksymalna suma od 0 do k <= i
        if (pre[i] < pre[i - 1])
            pre[i] = pre[i - 1];

    for (int i = n - 2; i >= 0; i--) // suf[i] = minimalna suma od k do n-1 dla k >= j
        if (suf[i] > suf[i + 1])
            suf[i] = suf[i + 1];

    // w tych nowych tablicach pre i suf chcemy, żeby i = j, bo to jest maksymalna wartość różnicy sum dla danego i, j
    // (pre[i] jest maksymalne, a suf[i] minimalne zatem pre[i] - suf[i] maksymalne)

    int max = suf[0] - pre[0];
    for(int i = 0; i < n; i++) // Szukamy maksimum liniowo, bo i tak już jest liniowo to czemu nie
        if (pre[i] - suf[i] > max)
            max = pre[i] - suf[i];

    return max;
}

int main(void)
{
    int n;
    scanf("%d", &n);
    int A[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &A[i]);

    printf("%d\n", maxdiff(A, n));

    return 0;
}