[백준 12015] 가장 긴 증가하는 부분 수열 3

문제 링크 => 12738번: 가장 긴 증가하는 부분 수열 3 (acmicpc.net)

12738번: 가장 긴 증가하는 부분 수열 3

---

가장 긴 증가하는 부분 수열 2 문제에서 수열의 값이 커진것을 제외하고 동일한 문제이다.

 

[백준 12015] 가장 긴 증가하는 부분 수열 2 :: M - J - C (tistory.com)

[백준 12015] 가장 긴 증가하는 부분 수열 2

위 링크의 코드에서 배열과 벡터의 type을 int 형에서 long long 형으로 변환만 해주면 끝이다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

long long arr[1000000];

void solve(int n) {
	vector<long long> v;

	for (int i = 0; i < n; i++) {
		int index = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
		if (index == v.size()) v.push_back(arr[i]);
		else if (index < v.size()) v[index] = arr[i];
	}

	cout << v.size() << endl;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	solve(n);
	
	return 0;
}