백준 12738. 가장 긴 증가하는 부분 수열 3(C++)

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

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

입력

• 첫째 줄에 수열 A의 크기가 주어진다.
• 둘째 줄에 수열 A를 이루고 있는 수가 주어진다.
•  

---

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		arr.push_back(tmp);
	}

• 입력을 받습니다.

	for (int i = 0; i < N; i++) {
		if (lis.back() < arr[i]) {
			lis.push_back(arr[i]);
		}
		else {
			int idx = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
			lis[idx] = arr[i];
		}
	}

• 입력 받은 수열을 새로운 배열에 저장을 합니다.
• 이 때 증가하는 순서로 저장을 하는데, 현재 검사하는 수가 저장한 수열의 마지막 수보다 크면, 뒤에 추가를 해주고
• 그렇지 않다면 저장한 수열 중 들어갈 수 있는 순서를 찾아 해당 위치에 저장을 해줍니다.

	cout << lis.size() << "\n";
	return 0;
}

• 위와 같은 방법으로 수열을 저장했다면, 새로 저장한 수열의 길이가 가장 긴 증가하는 부분 수열의 길이가 됩니다.