[POJ] 2533 Longest Ordered Subsequence.cpp

#include <cstdio>
using namespace std;
// Method 1
int main()
{
    int N;
    scanf("%d", &N);
    int num[1001], LIS[1001];
    int Max = 0;
    for (int i = 0; i < N; ++i) {
        scanf("%d", &num[i]);
        LIS[i] = 1;
        for (int j = 0; j < i ; ++j) {
            if (num[i] > num[j] && LIS[i] < LIS[j]+1)
                LIS[i] = LIS[j]+1;
        }
        if (LIS[i] > Max) Max = LIS[i];
    }
    printf("%d\n", Max);
}
// Method 2
int main()
{
    int N, a;
    scanf("%d", &N);
    int LIS[1001], Max = 0;
    while (N--) {
        scanf("%d", &a);

        int i = 0;
        while (a > LIS[i] && i < Max) ++i;

        if (i == Max) {
            LIS[Max] = a;
            ++Max;
        }
        else {
            if (a < LIS[i]) LIS[i] = a;
        }
    }
    printf("%d\n", Max);
}