AOJ

# # Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D

# # Time complexity

## # Solution 1

$O(NlogN)$

## # Solution 2

$O(N^2)$

# # Solution 1

#define N_MAX 100001

Int N;
vector<Int> A(N_MAX, -1);
vector<Int> L;

Int lis() {
L.push_back(A[0]); // base case
loop(n,1,N) { // general cases
if (last(L) < A[n]) L.push_back(A[n]);
else *lower_bound(span_all(L), A[n]) = A[n];
}
return len(L);
}

int main(void) {
cin >> N;
loop(i,0,N) cin >> A[i];
cout << lis() << endl;
}


# # Solution 2

No advantages over solution 1, but It may be useful for something.

#define N_MAX 10001

Int N;
vector<Int> A(N_MAX, -1);
vector<Int> L(N_MAX, 0);

Int solve() {
Int k, max_ = 0;
loop(n,1,N+1) {
k = 0;
loop(l,0,n) {
if (A[l] < A[n] && L[k] < L[l]) {
k = l;
}
}

L[n] = L[k] + 1;
if (L[n] > max_) max_ = L[n];
}

return max_;
}

int main(void) {
cin >> N;
loop(i,0,N) cin >> A[i];
cout << solve() << endl;
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!