/* université pierre et marie curie - christoph dürr et antoine roux - 2017
   http://www-desir.lip6.fr/~durrc/Iut/cpa/2017/tme5-progdyn/

   Programmation dynamique
*/

import java.util.*;
import java.io.*;


// cette classe est utilisée par stackingboxes
class Box implements Comparable<Box> {
    int w, h, d;
    Box(int w, int h, int d) {
        this.w = w;
        this.h = h;
        this.d = d;
    }
    public int compareTo(Box b) {
        // ordre lexicographique
        if (w != b.w)
            return w - b.w;
        if (h != b.h)
            return h - b.h;
        return d - b.d;
    }
}

// cette classe est utilisée par bridges
class Paire implements Comparable<Paire> {
    int x, y;
    Paire(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int compareTo(Paire p) {
        // ordre lexicographique
        if (x != p.x)
            return x - p.x;
        return y - p.y;
    }
}


class ProgDyn {

    static long sum(Scanner in) {
        int n = in.nextInt();
        long total = 0;                 // long  = 64 bits, log_2(1e12) < 40, donc ok
        while (n-->0)
            total += in.nextInt();
        return total;
    }


    /*               kadane

    trouve somme maximale dans L[i:j+1] avec i ≤ j

    problème:
        B[j] = max sum A[i:j+1] sur i ≤ j
        solution = max B
    cas de base:
        B[0] = A[0]
    pour i > 0:
        B[i] = A[i] + max(B[i - 1], 0)
    complexité:
        O(n) variables, récursion sur O(1) expressions
        complexité est O(n)
    */
    static long kadane(Scanner in) {
        int n = in.nextInt();
        long global_max = Long.MIN_VALUE;
        long local_max = 0;
        while (n-->0) {
            int xi = in.nextInt();
            if (local_max > 0)
                local_max += xi;
            else
                local_max = xi;
            if (local_max > global_max)
                global_max = local_max;
        }
        return global_max;
    }


    /*                coinchange

    :param v: table of non negative values
    :param C: target value
    :returns k: minimum number of coins that produce C
    :complexity: O(n*C)

    problème:
        A[i][m] = nb minimal de pièces parmi v[0] à v[i] pour constituer la valeur m
    cas de base:
        A[0][m] = m / v[0] si m est un multiple de v[0] sinon = infini
    pour i > 0:
        A[i][m] = min( A[i-1][m], A[i][m - v[i]] + 1 )  # attention au cas ou m < v[i]
    complexité:
        O(n*C) variables, récursions sur O(1) expressions
        complexité = O(n*C)

    */
    static int coinchange(Scanner in) {
        int n = in.nextInt();
        int C = in.nextInt();
        int v[] = new int[n];
        for (int i = 0; i < n; i++)
            v[i] = in.nextInt();
        int opt [] = new int[C + 1];
        for (int k = 1; k <= C; k++) {
            opt[k] = Integer.MAX_VALUE;
            for (int vi: v)
                if (vi <= k && opt[k - vi] + 1 < opt[k])
                    opt[k] = opt[k - vi] + 1;
        }
        return opt[C];
    }


    /*              longestincreasingsubsequence

    a = liste d'entrée

    pour chaque préfixe de a on maintient un tableau b
    b[k] = plus petite valeur v tel qu'il existe une
        sous-séquence strictement croissante dans ce préfixe
        de longueur k et qui termine par v
    pour chaque nouvelle valeur Ai, qui étend le préfixe,
        on peut améliorer b[k] à Ai
        en complétant avec Ai la liste de longueur k-1 terminant par b[k-1]
        et ceci dans le cas b[k-1] < Ai < b[k]
    l'indice k est trouvé par recherche dichotomique.

    complexité: O(n log n)
    */
    static int lis(int a[]) {
        int b[] = new int[a.length + 1];
        Arrays.fill(b, Integer.MAX_VALUE);
        b[0] = Integer.MIN_VALUE;
        int max = 0;
        for (int Ai: a) {
            int k = Arrays.binarySearch(b, 0, max + 2, Ai);
            if (k < 0) {
                int pos = -k - 1;
                if (b[pos - 1] < Ai)
                    b[pos] = Ai;
                if (pos > max)
                    max = pos;
            }
        }
        return max;
    }

    static int longestincreasingsubsequence(Scanner in) {
        int n = in.nextInt();
        int a[] = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = in.nextInt();
        return lis(a);
    }


    /*              stackingboxes

    problème:
        B = toutes les rotations des boîtes
        pour B de la plus grande à la plus petite boîte
        s[j] = empilement maximal des boites B[0] à B[j]
        solution = max s[j]
    récursion:
        s[j] = hauteur boîte j + max s[i]
        où la maximisation est prise sur les boîtes i < j,
        tel qu'on peut poser la boîte j sur la boîte i
    complexité:
        O(n) variable, récursion sur O(n) expressions
        total = O(n^2)

    */
    static int stackingboxes(Scanner in) {
        int n = in.nextInt();
        Box boxes [] = new Box[6 * n];
        int global_max = 0;
        int i = 0;
        for (int j = 0; j < n; j++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            boxes[i++] = new Box(a, b, c);
            boxes[i++] = new Box(a, c, b);
            boxes[i++] = new Box(b, a, c);
            boxes[i++] = new Box(b, c, a);
            boxes[i++] = new Box(c, b, a);
            boxes[i++] = new Box(c, a, b);
        }
        Arrays.sort(boxes);
        int opt[] = new int[6 * n];
        for (i = 6 * n - 1; i >= 0; i--) {
            int best = 0;
            for (int j = i + 1; j < 6*n; j++) {
                if (boxes[i].w < boxes[j].w &&
                    boxes[i].d < boxes[j].d &&
                    opt[j] > best)
                    best = opt[j];
            }
            opt[i] = boxes[i].h + best;
            if (opt[i] > global_max)
                global_max = opt[i];
        }
        return global_max;
    }


    /*              bridges

    Il existe une permutation L avec L[i]=j s'il existe un entier k tel que
    a[k] a le rang i dans a et b[k] le rang j dans b.

    Toute solution est une séquence croissante dans L et vice-versa.
    La difficulté est seulement de calculer L et puis d'appeler
    une procédure standard pour trouver une plus longue sous-séquence.

    complexité:
        calcul de L en O(n) (L est appelé rank dans le code)
        plus longue sous-séquence en O(n log n)
    */
    static int bridges(Scanner in) {
        int n = in.nextInt();
        Paire a[] = new Paire[n];
        Paire b[] = new Paire[n];
        for (int i=0; i<n; i++) {
            a[i] = new Paire(in.nextInt(), i);
            b[i] = new Paire(in.nextInt(), i);
        }
        Arrays.sort(a);
        Arrays.sort(b);
        int rankb [] = new int[n];
        for (int r = 0; r < n; r++)
            rankb[b[r].y] = r;
        int rank [] = new int[n];
        for (int r = 0; r < n; r++)
            rank[r] = rankb[a[r].y];
        return lis(rank);
    }


    /*                  knapsack

    p = poids des éléments, v = valeurs des éléments, capacity (ou C) = capacité knapsack
    complexité : O(n C)

    problème:
        Opt[i][c] = valeur maximum d'un ensemble de {0,..,i} de poids total au plus c
        solution = Opt[n-1][C]
    cas de base:
        Opt[0][c] = 0 si c < p[0] et = v[0] sinon
    récursion:
        Opt[i][c] = max(Opt[i - 1][c], Opt[i - 1][c - p[i]] + v[i])  # attention au cas c < p[i]
    complexité:
        O(n*C) variables, évaluation en temps constant
        total = O(n*C)
    */
    static int knapsack(Scanner in) {
        int n = in.nextInt();
        int capacity = in.nextInt();
        int p[] = new int[n];
        int v[] = new int[n];
        for (int i = 0; i < n ; i++) {
            p[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        int opt[][] = new int[n][capacity + 1];
        for (int c = p[0]; c <= capacity; c++)
            opt[0][c] = v[0];
        for (int i = 1; i < n; i++) {
            int k = Math.min(p[i], capacity);
            for (int c = 0; c < k; c++)
                opt[i][c] = opt[i-1][c];
            for (int c = k; c <= capacity; c++)
                opt[i][c] = Math.max(opt[i - 1][c], opt[i - 1][c - p[i]] + v[i]);
        }
        return opt[n-1][capacity];
    }


    /*              parenthesis

    On numérote les constantes dans L de 0 à n-1.
    La i-ème constante est val[i] =  L[2 * i]
    On numérote les opérateurs dans L de 0 à n-2.
    Le i-ème opérateur est op[i] = L[2 * i + 1]

    Une parenthèse gauche est devant une constante et une parenthèse droite après.

    A[i][j][v] = nombre de façons de placer les parenthèses sur l'expression
    entre la i-ème et la j-ème constante tel que la valeur de l'expression
    soit v.

    A[i][i][v] = 1 si val[i] est v et 0 sinon

    Pour i < j il faut itérer sur toutes les positions k du dernier opérateur appliqué :

    A[i][j][v] = la somme sur i ≤ k < j de A[i][k][a] * A[k+1][j][b] avec a op[k] b = v.

    L'idée clé est de traiter les couples (i,j) avec j-i croissant.

    complexité:
        O(n^3) variables, évaluation en temps constant
    */
    static long parenthesis(Scanner in) throws Exception {
        int n = in.nextInt();
        String [] L = new String[n];
        for (int i = 0; i < n; i++)
            L[i] = in.next();
        n = (n + 1) / 2;
        long A[][][] = new long[n][n][2];
        // --- cas de base
        for (int i = 0; i < n; i++) {
            if (L[2 * i].equals("true"))
                A[i][i][1] = 1;
            else
                A[i][i][0] = 1;
        }
        // --- récursion
        for (int diff = 1; diff < n; diff++)
            for (int i = 0; i < n - diff; i++) {
                int j = i + diff;
                for (int k = i; k < j; k++)
                    for (int a = 0; a < 2; a++)
                        for (int b = 0; b < 2; b++) {
                            int v = -1; // should never stay -1 on a correct input
                            switch (L[2 * k + 1]) {
                                case "and":
                                    v = a & b;
                                    break;
                                case "or":
                                    v = a | b;
                                    break;
                                case "xor":
                                    v = a ^ b;
                                    break;
                                default:
                                    throw new Exception("bad operator in input: " + L[2 * k + 1]);
                            }
                            A[i][j][v] = ( A[i][j][v] + A[i][k][a] * A[k + 1][j][b] ) % 100000007;
                        }
            }
        return A[0][n-1][1];
    }


    /*                      rowgame

    retourne la valeur que peut gagner le premier joueur
    si les deux joueurs jouent de manière optimale.

    problème:
        val[i][j] = valeur que le premier joueur peut obtenir
        si on joue sur l'intervalle L[i:j] (de i inclu à j exclu)
    pré-calcul:
        tot[i][j] = sum(L[i:j])
    cas de base:
        val[i][i] = 0 (car on joue sur un intervalle vide)
    récursion:
        val[i][j] = tot[i][j] - min( val[i + 1][j], val[i][j - 1])
    difficulté:
        évaluer val[i][j] dans l'ordre j-i croissant
    complexité:
        O(n^2) variables, évaluation en temps constant
    */
    static int rowgame(Scanner in) {
        int n = in.nextInt();
        int v[] = new int[n];
        for (int i = 0; i < n; i++)
            v[i] = in.nextInt();
        int val[][] = new int[n][n];
        int tot[][] = new int[n][n];

        // --- cas de base
        for (int i = 0; i < n; i++)
            tot[i][i] = val[i][i] = v[i];

        // --- récursion
        for (int diff = 1; diff < n; diff++)
            for (int i = 0; i < n - diff; i++) {
                int j = i + diff;
                tot[i][j] = tot[i][j-1] + tot[j][j];
                val[i][j] = tot[i][j] - Math.min( val[i + 1][j], val[i][j - 1]);
            }
        return val[0][n-1];
    }


    public static void main(String[] args) throws Exception {
        System.out.println(sum(new Scanner(new File("sum/big.in"))));
        System.out.println(kadane(new Scanner(new File("kadane/big.in"))));
        System.out.println(coinchange(new Scanner(new File("coinchange/big.in"))));
        System.out.println(longestincreasingsubsequence(new Scanner(new File("longestincreasingsubsequence/big.in"))));
        System.out.println(stackingboxes(new Scanner(new File("stackingboxes/big.in"))));
        System.out.println(bridges(new Scanner(new File("bridges/big.in"))));
        System.out.println(knapsack(new Scanner(new File("knapsack/big.in"))));
        System.out.println(parenthesis(new Scanner(new File("parenthesis/big.in"))));
        System.out.println(rowgame(new Scanner(new File("rowgame/big.in"))));
    }
}