来自 SPOJ，这是问题陈述。我从正常的 DP 解决方案开始，但这需要 n^2 时间，并且必然会超过时间限制。
我遇到了该问题的 nlogn 解决方案，这是解决方案。
如果我们只需要找到最长递增子序列的长度，或者如果您也必须找到其中一个序列，则该解决方案效果很好。但是如果你必须找到属于一个序列或另一个序列的所有元素，我做了一些存储和其他工作，我已经达到了这个解决方案。
现在这是 SPOJ 引擎所期望的，但是当我查看其他公认的解决方案时，我的程序需要 0.48 的时间，而其他程序需要低至 0.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;
}