가장 길게 증가하는 시퀀스 알고리즘 개선

Question

SPOJ에서 here is the problem statement. 정상적인 DP 솔루션으로 시작했지만 n^2 시간이 걸리고 제한 시간을 초과했습니다.

문제에 대한 nlogn 솔루션을 발견했으며 here is the solution for that입니다.

가장 길게 증가하는 서브 시퀀스의 길이를 찾거나 시퀀스 중 하나를 찾아야하는 경우 솔루션이 잘 작동합니다. 하지만 당신은 하나의 시퀀스 또는 기타의 일부인 모든 요소를 ​​찾을 수 있다면, 좀 스토리지 및 기타 물건을했고, SPOJ 엔진에 의해 예상있어 내가 지금이 this solution.

에 도달했습니다,하지만 난 볼 때 다른 받아 들여진 해결책에, 나의 프로그램은 다른 사람이 .04를 가지고 갈 때 .48 시간을 걸린다.

가능하면 누군가 내 솔루션을 개선 할 수있는 방법을 알려주고 싶습니다.

내 솔루션에서 수행하고있는 것은 출력 배열에서 현재 숫자 만 저장하고있는 것이 아니라 전체 목록을 저장하는 것입니다. 그리고 부모님은 각 숫자가 될 때마다 부모 모두를 유지하고 있습니다. 출력 배열의 일부.

최종 배열은 그 숫자가 LIS에 속하는지 아닌지에 대한 부울 값을 저장하는 최종 정수 배열입니다.

감사 그것은 ideone.com에 대한 링크를 따라서 자체 여기에 코드를 붙여 코드 동반되어야 함을 말한다

PS.

#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을 여러 번 호출하지 않는 것입니다.

최대 크기의 단일 배열을 사전 할당하고 내부에 할당 된 요소 수를 추적하여이 작업을 수행 할 수 있습니다.

재귀 함수 호출을 단일 반복 함수로 변경하면 함수를 호출하는 오버 헤드를 피할 수 있으므로 도움이됩니다.