Finding the largest increasing subsequence?

Question

C++ / C#

There is a simple task to find the largest increasing subsequence (on the screen)
informatics.mccme.ru/mod/statements/view3.php?id=7...
the solution of which is being automatically tested on some 18 different inputs
AND several solutions
for n^2 : e-maxx.ru/algo/longest_increasing_subseq_log#1
and for n lg n : e-maxx.ru/algo/longest_increasing_subseq_log#7
My solution for n^2 passes all 18 tests, the problem is in the second variant. Here is his
#include
#include
#include
#include
using namespace std;
FILE* input = freopen("input.txt", "r", stdin);
FILE* output = freopen("output.txt", "w", stdout);
int N, val, maxi = 0;
vectorv;
vector::iteratorub;
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); // passes all tests except the first one
//fprintf(output, "%i", maxi); // only passes the first test
return 0;
}
The problem is fixed in the comments and the question is: how can this happen? What did I miss?

Answer 1

If we compare the code with the algorithm, then the condition d[j-1] < a[i] is missing (apparently, in the code it should look like ub==v.begin() || ub[-1] < a[i] ). It seems that without it, the algorithm will look for a non-increasing, but non-decreasing sequence (but I'm not sure about this).