Поиск наибольшей возрастающей подпоследовательности?

Question

[Георгий]

Есть простенькая задачка на поиск наибольшей возрастающей подпоследовательности (на скрине)
informatics.mccme.ru/mod/statements/view3.php?id=7...
решение которой проходит автоматическое тестирование на неких 18 различных входах

И несколько вариантов решения
за n^2 : e-maxx.ru/algo/longest_increasing_subseq_log#1
и за n lg n : e-maxx.ru/algo/longest_increasing_subseq_log#7

Моё решение за n^2 проходит все 18 тестов, проблема во втором варианте. Вот его

#include
#include
#include
#include

using namespace std;

FILE* input = freopen("input.txt", "r", stdin);
FILE* output = freopen("output.txt", "w", stdout);

int main() {
int N, val, maxi = 0;
vector v;
vector::iterator ub;

fscanf(input, "%i ", &N);

for (int i = 0; i < N; i++) {
fscanf(input, "%i ", &val);
ub = upper_bound(v.begin(), v.end(), val);
if (ub != v.end())
*ub = val;
else
v.push_back(val);
}

for (int i = 0; i < v.size(); i++)
maxi = i;

fprintf(output, "%i", maxi + 1); // проходит все тесты кроме первого
//fprintf(output, "%i", maxi); // проходит только первый тест

return 0;
}

Проблема зафиксирована в комментариях и вопрос: как так может получаться? Что я упустил?

Comments

[Георгий]

Помоги мне, Тостер, ты моя единственная надежда, столько всего испробовал. Кстати, выходы 0 и 1 не проходили последний тест.

Answer 1

[Mrrl]

Если сравнивать код с алгоритмом, то пропущено условие d[j-1] < a[i] (видимо, в коде оно должно выглядеть, как ub==v.begin() || ub[-1] < a[i] ). Похоже, что без него алгоритм будет искать не возрастающую, а неубывающую последовательность (но я в этом не уверен).