uva 231 - Testing the CATCHER (version 2)

Problem link

/*

This is a more effective algorithm, its complexity is O(n.log(k)) where k is the length of the LIS

- The lis array contains the sequence.

- For each element of the array A, use binary search for the suitable position for that element in the lis array so that this array still a non-Decreasing array, call that position pos.

- Replace lis[pos] with A[i] for a better LDS later (if it has). This greedy step is important!

- If there is no suitable position for A[i], then A[i] must be the next smallest value in lis, hence add A[i] to lis.

- The largest number of elements of lis during this procedure is the result.

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 100000;
//-----------------------------
int a[maxn],lis[maxn];
int n,k;
//-----------------------------
void readfile() {
 n = 1;
 a[n]=k;
 int u;
 cin >> u;
 if (u==-1) return;
 while (u!=-1)
 {
  a[++n]=u;
  cin >> u;
 }
 return;
}
//-----------------------------
int find(int i, int j, int x) {
 int l,r,m;
 l = i; r = j;
 do
 {
  m = (l+r)/2;
  if (lis[m]<x) r = m;
  else l = m;
 } while (r-l>1);
 if (lis[l]<x) return(l);
 else if (lis[r]<x) return(r);
 else return(-1);
}
//-----------------------------
int solve() {
 int result = 1;
 memset(lis,0,sizeof(lis));
 for (int i=1; i<=n; i++)
 {
  int pos = find(1,result,a[i]);
  if (pos==-1) lis[++result] = a[i];
  else lis[pos] = a[i];
 }
 return(result);
}
//-----------------------------
int main() {
 int test=0;
 cin >> k;
 while (k!=-1)
 {
  test++;
  if (test>1) cout << endl;
  readfile();
  printf("Test #%d:\n",test);
  cout << "  maximum possible interceptions: ";
  cout << solve() << endl;
  cin >> k;
 }
 return 0;
}