/* Calculate a longest strictly decreasing subsequence (LDS). */

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


static void print_lds(int *x, int *p, int z) {
    if (p[z] > 0)
        print_lds(x, p, p[z]);
    printf("%d ", x[z]);
}


static int lds_length(int *x, int n) {
  
/*      Find the longest decreasing subsequence of x (1..n).             */
/*      Return the length as function value and call print_lds.          */

    int *c;
    int *p;
    int i, k;
    int answer, z;

    /* Subsidiary variables. */
    /* c stores optimal solutions up to and including each element */
    c = (int*)malloc((size_t)(n+1)*sizeof(int));
    /* p stores the index of the previous element in an optimal subsequence */
    p = (int*)malloc((size_t)(n+1)*sizeof(int));

    if (c == NULL || p == NULL)
    {
      fprintf(stderr,"Malloc failed in lds_length()\n");
      exit(1);
    }

    /* Initialisation: each element can be a trivial sequence length 1. */
    for (i = 1; i <= n; ++i) {
      c[i] = 1;
      p[i] = 0;
    }

    answer = 0; /* Length of optimal solution */
    z = 1;      /* Index of final element of optimal solution. */

    /* Main algorithm. */
    for (i = 1; i <= n; ++i) {
      for (k = 1; k < i; ++k) {
        /* Sequence must be decreasing. */
        if (x[i] < x[k]) {
          if (c[k]+1 > c[i]) {
            /* Record best solution up to and including this element. */
            c[i] = c[k]+1;
            p[i] = k;
            /* Update the optimal solution in substring X(1..i). */
            if (c[i] > answer) {
              answer = c[i];
              z = i;
            }
          }
        }
      }
    }

    /* Print the optimal solution. */
    print_lds(x, p, z);
    printf("\n");

    free((void*)c);
    free((void*)p);

    return answer;
}
    
/*****************************************************************/

int main(int argc, char *argv[]) {
    int *x;
    int i, n = 0;
    int answer;
    FILE *fp;

    if (argc != 2) {
        fprintf(stderr,"Usage: %s <filename>\n", argv[0]);
        fprintf(stderr,
"where <filename> has int n on line 1 and spaced n-int sequence on line 2.\n");
        exit(1);
    }

    /* Read in sequence of n integers from file. */
    if ((fp = fopen(argv[1], "r")) == NULL) {
        fprintf(stderr,"Can't open %s\n", argv[1]);
        exit(1);
    } else {
        fscanf(fp, "%d", &n);
        if (n == 0) exit(1);
        /* Allocate space for n integers in x. */
        x = (int*)malloc((size_t)(n+1)*sizeof(int));
        /* Dummy value x[0]: we consider first index as 1 for consistency. */
        x[0] = 0;
        for (i = 1; i <= n; ++i) {
            fscanf(fp, "%d", &x[i]);
        }
        if (feof(fp) != 0) {
            fprintf(stderr,"Format error in %s (%d integers).\n", argv[1], n);
            exit(1);
        }
        fclose(fp);
    }
    
    answer = lds_length(x, n);
    free((void*)x);

    printf("LDS is length %d\n", answer);

    return 0;
}