/* Calculate an increasing weighted subsequence (IWS)
   with the greatest sum of elements. */

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


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


static int iws_sum(int *x, int n) {
  
/*      Find an increasing subsequence of x (1..n) with greatest sum.    */
/*      Return the sum as function value and call print_lds.          */

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

    /* 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 iws_length()\n");
      exit(1);
    }

    /* Initialisation as singleton sequences */
    for (i = 1; i <= n; ++i) {
      c[i] = x[i];
      p[i] = 0;
    }

    answer = 0; /* Sum 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 increasing. */
          if (x[i] > x[k]) {
              k_sum = c[k]+x[i];
              k_index = k;
          } else {
              /* Consider this element on its own. */
              k_sum = x[i];
              k_index = 0;
          }
          if (k_sum > c[i]) {
            /* Record best solution up to and including this element. */
            c[i] = k_sum;
            p[i] = k_index;
            /* Update the optimal solution in substring X(1..i). */
            if (c[i] > answer) {
              answer = c[i];
              z = i;
            }
          }
      }
    }


    /* Print the optimal solution. */
    print_iws(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 = iws_sum(x, n);
    free((void*)x);

    printf("IWS sum is %d\n", answer);

    return 0;
}