// Prototype of dynamic programming for 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 IS that y[i] could be appended to. // See CSE 2320 Notes 01 for binSearchLast() k=binSearchLast(bsTabC,n+1,y[i]); C[i]=k+1; // Save length of LIS for y[i] j[i]=bsTabI[k]; // Predecessor of y[i] bsTabC[k+1]=y[i]; // Decrease value for this length IS bsTabI[k+1]=i; } printf(" i y C j\n"); printf("---------------\n"); for (i=1;i<=n;i++) printf("%3d %3d %3d %3d\n",i,y[i],C[i],j[i]); for (LISlength=n; bsTabC[LISlength]==999999; LISlength--) ; printf(" i bsTabC bsTabI\n"); printf("-----------------\n"); for (i=1;i<=LISlength;i++) printf("%3d %6d %6d\n",i,bsTabC[i],bsTabI[i]); printf("Length of LIS is %d\n",LISlength); printf("LIS reversed\n"); for (i=bsTabI[LISlength]; i>0; i=j[i]) printf("%d\n",y[i]); free(y); free(bsTabC); free(bsTabI); free(C); free(j); }