DPL_1_D Longest Increasing Subsequences

Calendar Clock iconCalendar Clock icon

AOJ

Table of contents

# Problem

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

# Time complexity

# Solution 1

O(NlogN)O(NlogN)

# Solution 2

O(N2)O(N^2)

# Solution 1

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
#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.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
#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;
}

Shun

Github Circle icon

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!

Comments