實作頗標準的 Patience Sorting。
Imeplement standard patience sorting.
Patience Sorting - Wikipedia (En)
演算法筆記 - Longest Increasing Subsequence (Zh)

UVa Link

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 1000000, MAX_SIZE = 1000;

int main() {
	int size = 0, tmpIn, lastIndice = 0;
	int in[MAX_SIZE], tmp[MAX_SIZE], pos[MAX_SIZE] = { 0 };
	fill(tmp, tmp + MAX_SIZE, INF);

	while (scanf("%d", &tmpIn) == 1) in[size++] = tmpIn; // End output with ^D

	for (int i = 0; i < size; i++) {
		int *insertPtr = lower_bound(tmp, tmp + size, in[i]);
		*insertPtr = in[i];
		pos[i] = insertPtr - tmp; // Save inserted position
		if (pos[i] > lastIndice) lastIndice = pos[i];
	}

	printf("%d\n-\n", lastIndice + 1);

	int posCount = lastIndice;
	for (int i = size - 1; i >= 0; i--) {
		if (pos[i] == posCount) {
			tmp[posCount--] = in[i]; // Reuse tmp, heh
		}
	}

	for (int i = 0; i < lastIndice + 1; i++) printf("%d ", tmp[i]);
	return 0;
}