// Prototype of dynamic programming for Strictest Longest Increasing Subsequence // Based on D. Gries, The Science of Programming, p. 262 // which is based on M. Fredman, Discrete Mathematics 11 (1975), // 29-35. // See CSE 2320 Notes 07 #include #include int binSearchLast(int *a,int n,int key) { // Input: int array a[] with n elements in ascending order. // int key to find. // Output: Returns subscript of the last a element <= key. // Returns -1 if keyhigh, low==high+1 and a[high]<=key and a[low]>key. while (low<=high) { mid=(low+high)/2; if (a[mid]<=key) low=mid+1; else high=mid-1; } return high; } int main() { // Get input sequence int n; int *y,*bsTabC,*bsTabI,*C,*j; int i,k,LISlength; // Get input sequence scanf("%d",&n); y=(int*) malloc((n+1)*sizeof(int)); bsTabC=(int*) malloc((n+1)*sizeof(int)); bsTabI=(int*) malloc((n+1)*sizeof(int)); C=(int*) malloc((n+1)*sizeof(int)); j=(int*) malloc((n+1)*sizeof(int)); if (!y || !bsTabC || !bsTabI || !C || !j) { printf("malloc fail %d\n",__LINE__); exit(0); } for (i=1;i<=n;i++) scanf("%d",y+i); // Initialize table for binary search for DP bsTabC[0]=(-999999); // Must be smaller than all input values. bsTabI[0]=0; // Index of predecessor (0=grounded) for (i=1;i<=n;i++) bsTabC[i]=999999; // Must be larger than all input values. C[0]=0; // DP base case j[0]=0; for (i=1;i<=n;i++) { // Find SIS that y[i] could be appended to. // See CSE 2320 Notes 01 for binSearchLast() k=binSearchLast(bsTabC,n+1,y[i]); // y[i] only matters if it is not already in table. if (bsTabC[k]0; i=j[i]) printf("%d\n",y[i]); free(y); free(bsTabC); free(bsTabI); free(C); free(j); }