#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXVAL 99
#define PLUS_INFTY 2147483647
#define MINUS_INFTY -2147483648

void genArrays ( int *A, int *B, int n )
{
   int i;

   for (i=0; i<n; ++i) {
      A[i] = 1 + rand() % MAXVAL;     /* All A[i] are positive */
      B[i] = 1 + rand() % MAXVAL;
      if (rand() % 2) B[i] = -B[i];   /* B[i] may be positive or negative */
   }
}

/* Standard left-to-right associative difference */
int stdDiff ( int *A, int n )
{
   int i, diff;

   if (n == 0) return 0;
   diff = A[0];
   for (i=1; i<n; ++i) diff -= A[i];
   return diff;
}

/* Maxminusian difference for positive integers */
int MDP_Pos ( int *A, int n )
{
   int i, diff;

   if (n == 0) return 0;
   if (n == 1) return A[0];
   diff = A[0] - A[1];
   for (i=2; i<n; ++i) diff += A[i];
   return diff;
}

void prnInt ( int x )
{
   if (x >= 0) printf("%d", x); else printf("(%d)", x);
}

/* For positive integers, the left-to-right associative method is also
   the Minminusian difference. */
void prn1 ( int *A, int n )
{
   int i;

   printf("    Left-to-right associative difference:\n      ");
   if (n == 0) { printf("0\n"); return; }
   prnInt(A[0]);
   for (i=1; i<n; ++i) {
      printf("-"); prnInt(A[i]);
   }
   printf(" = ");
   printf("%d\n", stdDiff(A,n));
}

/* In Maxminusia, this is A[0] - (A[1] - A[2] - A[3] - ... - A[n-1]) for
   positive integers. */
void prn2 ( int *A, int n )
{
   int i;

   printf("    Maximinusian difference of positive integers:\n      ");
   if (n == 0) { printf("0\n"); return; }
   if (n == 1) {
      prnInt(A[0]); printf("-"); prnInt(A[1]);
      printf(" = %d", MDP_Pos(A,n));
      return;
   }
   prnInt(A[0]); printf("-"); prnInt(A[1]);
   for (i=2; i<n; ++i) { printf("+"); prnInt(A[i]); }
   printf(" = "); printf("%d\n", MDP_Pos(A,n));
}

void prn4 ( int *, int **, int **, int, int );

void prn3 ( int *A, int **U, int **V, int L, int R )
{
   if (L == R) prnInt(A[L]);
   else {
      printf("(");
      prn3(A,U,V,L,U[L][R]);
      printf("-");
      prn4(A,U,V,U[L][R]+1,R);
      printf(")");
   }
}

void prn4 ( int *A, int **U, int **V, int L, int R )
{
   if (L == R) prnInt(A[L]);
   else {
      printf("(");
      prn4(A,U,V,L,V[L][R]);
      printf("-");
      prn3(A,U,V,V[L][R]+1,R);
      printf(")");
   }
}

/* Simultaneous solution of Maxminusian and Minminusian difference problems.
   Explicit parenthesizations are also computed. */
void MDP ( int *A, int n )
{
   int **maxd,    /* To store the Maxminusian difference of A[i...j] */
       **mind,    /* To store the Minminusian difference of A[i...j] */
       **U,       /* To store the best break point for Maxminusian difference */
       **V;       /* To store the best break point for Minminusian difference */
   int i, j, k, l, max, maxidx, min, minidx, diff;

   /* Allocate memory*/
   maxd = (int **)malloc(n * sizeof(int *));
   mind = (int **)malloc(n * sizeof(int *));
   U = (int **)malloc(n * sizeof(int *));
   V = (int **)malloc(n * sizeof(int *));
   for (i=0; i<n; ++i) {
      maxd[i] = (int *)malloc(n * sizeof(int));
      mind[i] = (int *)malloc(n * sizeof(int));
      U[i] = (int *)malloc(n * sizeof(int));
      V[i] = (int *)malloc(n * sizeof(int));
   }

   /* One element case */
   for (i=0; i<n; ++i) {
      maxd[i][i] = mind[i][i] = A[i];
      U[i][i] = V[i][i] = i;
   }

   /* For more than one elements */
   for (l=1; l<n; ++l) {
      for (i=0,j=l; j<n; ++i,++j) {
         /* Compute maxd[i][j] and mind[i][j] simultaneously */
         max = MINUS_INFTY; min = PLUS_INFTY;
         for (k=i; k<j; ++k) {
            diff = maxd[i][k] - mind[k+1][j];
            if (diff >= max) { max = diff; maxidx = k; }
            diff = mind[i][k] - maxd[k+1][j];
            if (diff <= min) { min = diff; minidx = k; }
         }
         maxd[i][j] = max; U[i][j] = maxidx;
         mind[i][j] = min; V[i][j] = minidx;
      }
   }

   printf("    Dynamic-programming solution (Maxminusia):\n      ");
   prn3(A,U,V,0,n-1);
   printf(" = %d\n", maxd[0][n-1]);

   printf("    Dynamic-programming solution (Minminusia):\n      ");
   prn4(A,U,V,0,n-1);
   printf(" = %d\n", mind[0][n-1]);

   /* Coutesy: free locally allocated memory */
   for (i=0; i<n; ++i) {
      free(maxd[i]); free(mind[i]); free(U[i]); free(V[i]);
   }
   free(maxd); free(mind); free(U); free(V);
}

/* This is the linear-time greedy solution */
void prn5 ( int *A, int n )
{
   int i, max, min;

   if (n == 0) max = min = 0;
   else if (n == 1) max = min = A[0];
   else {
      max = min = A[0] - A[1];
      for (i=2; i<n; ++i) {
         if (A[i] >= 0) { max += A[i]; min -= A[i]; }
         else { max -= A[i]; min += A[i]; }
      }
   }
   printf("    Greedy solution (Maxminusia): %d\n", max);
   printf("    Greedy solution (Minminusia): %d\n", min);
}

int main ( int argc, char *argv[] )
{
   int n, *A, *B;

   srand((unsigned int)time(NULL));
   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);

   A = (int *)malloc(n * sizeof(int));
   B = (int *)malloc(n * sizeof(int));

   genArrays(A,B,n);

   printf("\n*** Dealing with positive integers only...\n");
   prn1(A,n);
   prn2(A,n);
   MDP(A,n);
   prn5(A,n);

   printf("\n*** Dealing with arbitrary integers...\n");
   prn1(B,n);
   MDP(B,n);
   prn5(B,n);

   exit(0);
}