uva 231 - Testing the CATCHER

Problem link

/*

This is the lazy DP version, the complexity of this approach is O(n^2). But it still got AC for this problem.

l[i] is the length of the LDS(LIS) ends at i. Therefor:

l[i] = 1 as initial.

l[i] = max(l[i], l[j] + 1 for j from 1 to i-1 and a[j]>=a[i])

Note: This problem is non-Decreasing Subsequence.

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 10000;
//-----------------------------
int a[maxn],l[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 solve() {
 int result = 1;
 memset(l,0,sizeof(l));
 l[1] = 1; 
 for (int i=2; i<=n; i++)
 {
  l[i]=1;
  for (int j=1; j<=i-1; j++)
   if (a[j]>=a[i]) l[i]=max(l[i],l[j]+1);
  if (l[i]>result) result = l[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;
}
//-----------------------------