改進最長遞增順序算法

Question

從SPOJ，here is the problem statement.我開始使用正常的DP解決方案，但這需要n^2次，並且必然會超出時間限制。

我遇到了nlogn問題的解決方案和here is the solution for that。

如果我們只需要找到最長的增長子序列的長度，或者您也必須找到其中一個序列，那麼該解決方案就可以很好地工作。但是，如果你必須找到所有的都是一個序列或其他的部分元素，我做了一些存儲和其他的東西，我已經達到this solution.

現在這個由SPOJ引擎得到了預期，但是當我看在其他可接受的解決方案中，我的程序花費了.48時間，其他時間則低至.04。

我想知道，如果可能的話，有人能告訴我如何改進我的解決方案嗎？

我在我的解決方案中做的是，在輸出數組中，我不僅存儲當前數字，而且存儲整個列表，並且在父項中，我維護所有項的父項，因爲每個數字都變成輸出數組的一部分。

最終數組只不過是最後一個整數數組，它存儲了布爾值，該數字是否屬於LIS。

感謝

PS它說，鏈接ideone.com必須由代碼陪同，因此在這裏粘貼代碼本身。

#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

一個建議（這可能只會幫助少量）將避免調用calloc這麼多次。

您可以通過預先分配最大大小的單個數組並且跟蹤其中已分配了多少個元素來完成此操作。

它也可能有助於將遞歸函數調用更改爲單個迭代函數，因爲這可以避免調用該函數的開銷。