Uva 231 Solution

#include<bits/stdc++.h>
#define N 1000000
using namespace std;
const int inf = 2e9;
int a[N];
int lis(int n)
{
    int I[n+1], i;
    I[0] = -inf;

    for(i=1;i<=n;i++)
        I[i] = inf;

    int length = 0;

    for(i=0;i<n;i++)
    {
        int low = 0, high = length, mid = 0;
        while(low <= high)
        {
            mid = (low+high)/2;
            if(I[mid] < a[i])
                low = mid + 1;
            else
                high = mid - 1;
        }
        I[low] = a[i];
        if(length < low)
            length = low;
    }

    return length;
}
int main()
{
    int i = 0, j = 1;
    while(cin >> a[0] && a[0] != -1)
    {
        i = 1;
        while(cin >> a[i] && a[i] != -1)
        {
            i++;
        }
        reverse(a, a+i);
        int result = lis(i);
        if(j > 1)
            cout << "\n";
        cout << "Test #" << j++ << ":\n";
        cout << "  maximum possible interceptions: " << result << "\n";
    }

    return 0;
}