Improving the Longest Increasing Sequence Algorithm

Question

From SPOJ, here is the problem statement. I started off with the normal DP solution, but that was going to take n^2 time and was bound to exceed the time limit.

I came across the nlogn solution to the problem and here is the solution for that.

The solution works well if we just have to find the length of longest increasing subsequence, or if you have to find one of the sequences too. But If you have to find all the elements that are part of one sequence or the other, I did some storage and other stuff and I have reached this solution.

Now this got expected by the SPOJ engine, but when I look at other accepted solutions, my program take .48 time where as others take as low as .04.

I want to know, if possible, can someone tell me how can I improve my solution?

What I am doing in my solution is that, in the output array, I am not only storing the current number, but the entire list, and in the parent, I am maintaining the parent of all, as each number becomes part of the output array.

The final array is nothing more than the final integer array, that stores boolean values, of whether that number belongs in the LIS or not.

Thanks

PS It says that Links to ideone.com must be accompanied by code, hence pasting the code here itself.

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

int count;

struct node{
    int value;
    struct node* next;
};

int constructFinal(int *final,struct node **parent,struct node **output,int value){
    if(final[value - 1] == 1)
        return 0;
    final[value - 1] = 1;
    count++;
    struct node* temp;
    temp = parent[value-1];
    while(temp!= NULL){
        constructFinal(final,parent,output,temp->value);
        temp = temp->next;
    }
}

int findIndex(int currentElement,struct node** output,int lower,int upper){
    if(lower >= upper)
        return lower;
    int mid =lower + ( upper - lower )/2;
    if(output[mid]->value < currentElement)
        return findIndex(currentElement,output,mid+1,upper);
    else if(output[mid]->value > currentElement)
        return findIndex(currentElement,output,lower,mid);
}   

int main(){
    int numOfInp,sizeOfInp,i,currentElement,sizeOfOut,indexBinary,indexAdded;
    struct node *temp,*tempIter;
    numOfInp=1;
    while(numOfInp--){
        scanf("%d",&sizeOfInp);
        struct node **output; // if I initialise normal initialisation, I may not get the data as 0 by default, hence callocing
        struct node **parent;
        int *input;
        input = (int *)calloc(sizeOfInp,sizeof(int));
        for(i=0 ; i< sizeOfInp ; i++)
            scanf("%d",&input[i]);

        parent = (struct node**)calloc(sizeOfInp, sizeof(struct node*));

        output = (struct node**)calloc(sizeOfInp, sizeof(struct node*));
        sizeOfOut = 0;
        for(i=0;i<sizeOfInp;i++){
            indexBinary = -1;
            currentElement = input[i];
            if(sizeOfOut == 0){
                output[sizeOfOut] = (struct node*)calloc(1,sizeof(struct node));
                output[sizeOfOut]->value = currentElement;
                indexAdded = sizeOfOut;
                sizeOfOut++;
            }
            else{
                if(currentElement > output[sizeOfOut-1]->value){
                    output[sizeOfOut] = (struct node*)calloc(1,sizeof(struct node));
                    output[sizeOfOut]->value = currentElement;
                    indexAdded = sizeOfOut;
                    sizeOfOut++;
                }
                else{
                    indexBinary = findIndex(currentElement,output,0,sizeOfOut-1);
                    temp = (struct node*)calloc(1,sizeof(struct node));
                    temp->next = output[indexBinary];
                    output[indexBinary] = temp;
                    output[indexBinary]->value = currentElement;
                    indexAdded = indexBinary;
                }
            }

            //parent[currentElement-1] = (struct node*)calloc(sizeof(struct node));
            if(indexAdded > 0){
                tempIter = output[indexAdded-1];
                while(tempIter != 0 && tempIter->value < currentElement){               //for all the elements in the previous bucket
                    temp = (struct node*)calloc(1,sizeof(struct node)); //add the values to parent
                    temp->next = parent[currentElement-1];
                    parent[currentElement-1] = temp;
                    parent[currentElement-1]->value = tempIter ->value;
                    tempIter = tempIter->next;
                }
            }
            else{
                parent[currentElement-1] = NULL;    // these are the elements in the first bucket of output
            }
        }

        int *final;
        final = (int*)calloc(sizeOfInp,sizeof(int));
        temp = output[sizeOfOut -1];
        count=0;
        while(temp != NULL){
            constructFinal(final,parent,output,temp->value);
            temp=temp->next;
        }
        printf("%d\n",count);
        for(i=0;i<sizeOfInp;i++)
            if(final[i]==1)
                printf("%d ",i+1);
        printf("\n");
        free(output);
        free(parent);

    }
    return 0;
}

Answer 1

One suggestion (that will probably only help a small amount) would be to avoid calling calloc so many times.

You can do this by preallocating a single array of the maximum size and keeping track of how many elements have been allocated inside it.

It may also help to change your recursive function calls into single iterative functions as this may avoid the overhead of calling the function.