[C++] Longest Increasing Subsequence / codeforces-486-E

https://codeforces.com/problemset/problem/486/E

Problem - 486E - Codeforces

// Longest Increasing Subsequence
#include <bits/stdc++.h>

using namespace std;

int n;
int A[100005];		// 숫자를 저장할 배열
int L[100005];		// LIS(정답)를 저장할 배열
int B[100005];		// 역방향으로 숫자를 저장할 배열
int M[100005];		// 임시적으로 저장할 배열
int R[100005];		// 역방향으로 LIS를 저장할 배열
int O[100005];		// LIS를 계산할 때 사용될 수들 저장
int LeftMax[100005];		// 왼쪽 전부를 보고 LIS 들어가는 것 중 max
int RightMin[100005];		

vector<int> Last;	// 마지막 index를 기억하는 vector. 이 vector의 인덱스가 개수

void LIS(int X[], int D[], int n)
{
	int i;
	vector<int>::iterator it;		// iterator는 pointer와 같은 개념
	Last.clear();
	Last.push_back(-1);
	for (i = 1; i <= n; i++) {
		if (Last.back() < X[i])
			Last.push_back(X[i]);
		it = lower_bound(Last.begin(), Last.end(), X[i]);	// 크거나 같은 것 중에 제일 작은 것.
		*it = X[i];
		D[i] = it - Last.begin();
	}
}

int main()
{
	// LMax는 좌측부터 시작해서 최대 LIS값
	int i, LMax;
	LMax = 0;
	cin >> n;
	
	for (i = 1; i <= n; i++) 
		cin >> A[i];

	LIS(A, L, n);

	for (i = 1; i <= n; i++) {
		//B[i] = 1000000 - A[n - i + 1];
		B[n - i + 1] = 1000000 - A[i];
	}

	LIS(B, M, n);
	for (i = 1; i <= n; i++) {
		R[i] = M[n - i + 1];
		//cout << R[i] << " ";
	}

	for (i = 1; i <= n; i++) {
		LMax = max(LMax, L[i]);
		O[i] = 1;
	}

	for (i = 1; i <= n; i++) {
		if (L[i] + R[i] == LMax + 1)
			// 3인 경우는 LIS를 계산할 때 사용된다.
			O[i] = 3;
	}

	LeftMax[0] = -1;
	for (i = 1; i <= n; i++)
		if (O[i] == 3)
			LeftMax[i] = max(LeftMax[i - 1], A[i]);
		else
			LeftMax[i] = LeftMax[i - 1];

	RightMin[n + 1] = 1000000;
	for (i = n; i >= 1; i--)
		if (O[i] == 3)
			//RightMin[i] = min(RightMin[i + 1], B[i]);
			RightMin[i] = min(RightMin[i + 1], A[i]);
		else
			RightMin[i] = RightMin[i + 1];

	for (i = 1; i <= n; i++)
		if (O[i] == 3 && (LeftMax[i - 1] >= A[i] || RightMin[i + 1] <= A[i]))
			O[i] = 2;

	for (i = 1; i <= n; i++)
		cout << O[i];

	return 0;
}