What Goes Up
Write a program that will select the longest strictly increasing subsequence from a sequence of integers.
Input
The input file will contain a sequence of integers (positive, negative, and/or zero). Each line of the input file will contain one integer.
Output
The output for this program will be a line indicating the length of the longest subsequence, a newline, a dash character (‘-‘), a newline, and then the subsequence itself printed with one integer per line. If the input contains more than one longest subsequence, the output file should print the one that occurs last in the input file.
Notice that the second 8 was not included — the subsequence must be strictly increasing.
Sample Input
-7 10 9 2 3 8 8 1
Sample Output
4 - -7 2 3 8
C Code
#include<stdio.h>
#define MIN(a, b) (a>b?b:)
#define MAXN 1000000
int SEQ[MAXN];
int TEMP[MAXN];
int Par[MAXN];
int N, MAX, LIMIT;
int FIND_BEST(int key) {
int lo, up, mid;
lo = 1; up = LIMIT;
mid = (lo + up) / 2;
if(SEQ[TEMP[1]] >key)
return 1;
else if(SEQ[TEMP[LIMIT]]<key)
return LIMIT+1;
while(lo <up && SEQ[TEMP[mid]] != key) {
if(SEQ[TEMP[mid]]<key)
lo = mid+1;
else if(SEQ[TEMP[mid]]>key) {
if(SEQ[TEMP[mid-1]]<key)
return mid;
up = mid-1;
}
mid = (lo + up ) / 2;
}
return mid;
}
void FIND_LIS() {
int pos, i;
TEMP[1] = 0;
LIMIT = 1;
Par[0] = -1;
TEMP[0] = -1;
for(i = 1; i<N; i++) {
pos = FIND_BEST(SEQ[i]);
if(pos>LIMIT) {
LIMIT = pos;
TEMP[pos] = i;
Par[i] = TEMP[pos-1];
}
else if(SEQ[TEMP[pos]] > SEQ[i]){
TEMP[pos] = i;
Par[i] = TEMP[pos-1];
}
}
}
void Print(int n) {
if(Par[n] == -1) {
printf("%d\n",SEQ[n]);
return;
}
Print(Par[n]);
printf("%d\n",SEQ[n]);
}
void main() {
N = 0;
int n;
// freopen("z:\\h.txt","r",stdin);
while(scanf("%d",&n) == 1) {
SEQ[N++] = n;
}
FIND_LIS();
printf("%d\n",LIMIT);
printf("-\n");
Print(TEMP[LIMIT]);
}
