C++ 알고리즘 - 11053 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

 

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

/******** 전역변수 ********/


/******** 함    수 ********/


int main(void) {
	/******** C++ INIT ********/
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	/******** 지역변수 ********/
	int input1;
	int input2;
	int cnt;

	vector<int> v;
	vector<int> v2;


	/******** 구    현 ********/
	cin >> input1;
	for (int i = 0; i < input1; i++) {
		cin >> input2;
		v.push_back(input2);
	}

	// 벡터 input1 크기만큼 0으로 초기화
	v2.assign(input1, 0);

	// 수열 찾기 로직
	for (int i = 0; i < v.size(); i++) {
		cnt = 0;

		// 가장 첫번째 수부터 i까지 탐색
		for (int j = 0; j < i; j++) {

			// j번째 수가 i번째 수보다 작다면
			if (v[j] < v[i]) {

				// cnt : j번째 수로 만들 수 있는 수열의 최대 값 (초기값 : 0)
				// v2[j] : j번째 수까지 만들 수 있는 수열의 최대 값
				if (cnt < v2[j]) 
					cnt = v2[j];
			}
		}

		// 마지막 위치도 수열에 포함되기 때문에 +1
		v2[i] = cnt + 1;
	}

	// 벡터 내 최대값 출력
	cout << *max_element(v2.begin(), v2.end()) << endl;

}