UVa : 497 (Strategic Defense Initiative )

// http://uva.onlinejudge.org/external/4/497.html
// Runtime: 0.016s
// Tag: LIS, Dp


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long

const double EPS = 1e-9;
inline bool Equal(double a, double b) { return abs(a-b) < EPS; }
inline LL Power(int b, int p) { LL ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; }
const int dr [] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dc [] = {0, 1, 1, 1, 0, -1, -1, -1};

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(i, x) for(typeof (x.begin()) i = x.begin(); i != x.end (); i++)
#define Set(a, s) memset(a, s, sizeof (a))
#define max(a, b)  (a < b ? b : a)
#define min(a, b)  (a > b ? b : a)

using namespace std;

// @BEGIN_OF_SOURCE_CODE
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

// Dp: O(n^2)
void get_lis_length (int *a, int length)
{
	int best [length]; // length of LIS upto using this num
	int prev_element [length]; // previous elements index
	for ( int i = 0; i < length; i++ )
	{
		best [i] = 1;
		prev_element [i] = i;
	}
	// first number always right, i = 1
	for ( int i = 1; i < length; i++ )
	{
		for ( int j = 0; j < i; j++ )
		{
			if ( a [i] > a [j] && best [i] < best [j] + 1 )
			{
				best [i] = best [j] + 1;
				prev_element [i] = j;
			}
		}
	}
	int lis_length = 0;
	int numIndex = -1;
	for ( int i = 0; i < length; i++ ) {
		if ( lis_length < best [i] ) {
			lis_length = best [i];
			numIndex = i;
		}
	}

	printf ("Max hits: %d\n", lis_length);

	vector <int> output;

	while ( prev_element [numIndex] != numIndex ) {
		output.push_back(a [numIndex]);
		numIndex = prev_element [numIndex];
	}

	output.push_back(a [numIndex]);
	reverse(output.begin(), output.end());

	Fs (i, output) printf ("%d\n", output [i]);
}
int main ()
{
	int testCase; scanf ("%d", &testCase);
	getchar ();
	char ch [20]; gets (ch);

	bool blank = false;

	int nums [10000];

	while ( testCase-- ) {
		int ind = 0;

		while ( gets (ch) && strlen (ch) ) {
			nums [ind++] = atoi (ch);
		}

		if ( blank ) printf ("\n");
		blank = true;

		get_lis_length (nums, ind);

	}

	return 0;
}
// @END_OF_SOURCE_CODE