2533 Longest Ordered Subsequence

2533 Longest Ordered Subsequence
与えられた数列から昇順の部分数列を取り出したとき、
要素数最大のものの大きさを答える問題。


PKUに興味を持つきっかけになった1159 Palindromeに似てるなぁ、
と思ってDPでやるのだろうと思ったけど挫折。
思考錯誤した末、ヘンテコなアルゴリズムでゴリ押しして通った。
（最初はTLEだったけど無駄削って何とか1250MS/2000MS）


数列をseq[N]に格納。数列中の位置をindex、それまでの部分数列の長さを
lenとして、キューにpair(index, len)を突っ込んで、そこからpopした
pair pに対して、部分数列が長くなるi(p.first < i < N)をpair(i, len+1)
としてキューにpushする。先日泣きながら習得したダイクストラ法をヒントに…


めんどくさい上に理解し辛い。。。


以下通ったソースコード

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

int main() {
    int N;
    cin >> N;
    int seq[N];
    for (int i = 0; i < N; ++i) {
	cin >> seq[i];
    }
    queue<pair<int, int> > q;
    for (int i = 0; i < N; ++i) {
	q.push(make_pair(i, 1));
    }
    int max = 0;
    int check[N];
    memset(check, 0, sizeof(check));
    while (!q.empty()) {
	int pos = q.front().first;
	int len = q.front().second;
	max = max>len?max:len;
	q.pop();
	if (check[pos] >= len) continue;
	check[pos] = len;
	for (int i = pos+1; i < N; ++i) {
	    if (seq[pos] < seq[i]) {
		if (check[i] >= (len + 1)) continue;
		q.push(make_pair(i, len+1));
	    }
	}
    }
    cout << max << endl;
}

以下通らなかったオーダー的にはいいセンいってそうなやつ

#include<iostream>
#include<stack>
#include<algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    int seq[N];
    for (int i = 0; i < N; ++i) {
	cin >> seq[i];
    }
    int maxlen = 0;
    stack<int> stk;
    for (int i = 0; i < N; ++i) {
	if (stk.empty()) {
	    stk.push(seq[i]);
	} else if (stk.top() < seq[i]) {
	    stk.push(seq[i]);
	} else {
	    maxlen = max(maxlen, (int)stk.size());
	    while (!stk.empty() && stk.top() >= seq[i]) {
		stk.pop();
	    }
	    stk.push(seq[i]);
	}
    }
    maxlen = max(maxlen, (int)stk.size());
    cout << maxlen << endl;
}