實作頗標準的 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;
}