#include "common.h"

int main(int ac, char *av[])
{
    uint max_length, end_of_lis;
    int *A, *length, *predecessor, i, j, k, l;

    if (ac < 2)
        ERR_MESG("Usage: longest-increasing-subsequence a1 a2 ...");

    if (NULL == (A = Malloc(ac-1, int)) ||
        NULL == (length = Malloc(ac-1, int)) ||
        NULL == (predecessor = Malloc(ac-1, int)))
        ERR_MESG("longest-increasing-subsequence: out of memory\n");

    /* Initialisation */
    for (i = 0; i < ac-1; i++) {
        A[i] = atoi(av[i+1]);
        length[i] = 1; /* just itself */
        predecessor[i] = -1;
    }

    /* Dynamic programming algorithm */
    for (k = 1; k < ac-1; k++)
        for (j = 0; j < k; j++)
            if (A[k] > A[j] &&
                length[k] < length[j] + 1) { /* try <= instead of < */
                length[k] = length[j] + 1;
                predecessor[k] = j;
            }

    k--;
    max_length = length[k];
    end_of_lis = k--;
    while (k >= 0) {
        if (length[k] > max_length) { /* try >= instead of > */
            max_length = length[k];
            end_of_lis = k;
        }
        k--;
    }

    /* Print the actual LIS: sorry this is confusing */
    l = length[end_of_lis];
    printf("Longest increasing subsequence (%d elements): ", l);
    for (i = l-1, j = end_of_lis;
         j != -1 && i >= 0;
         i--, j = predecessor[j])
        /* Being lazy, sorry: reusing the length array to store actual lis */
        length[i] = j;
    assert(i == -1 && j == -1);
    for (i = 0; i < l; i++)
        printf("A[%d] = %d,   ", length[i], A[length[i]]);
    putchar('\n');

    free(A); free(length); free(predecessor);
    return 0;
}