LDS(Longest Decreasing Sequence). 최장 감소 수열

LDS.cc

#include<iostream>

using namespace std;

int main()
{
	int n; //입력하는 데이터 갯수
	int ind = 0; //d 인덱스
	int arr[1000] = { 0 };
	int d[1000] = { 0 };
	
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	for (int i = 0; i < n; i++)
	{
		if (ind == 0)//아무것도 없으면
			d[ind++] = arr[i];//배열에 넣는다.
		else
		{
			if (d[ind - 1] > arr[i])
			{
				d[ind++] = arr[i];
			}
			else
			{
				//배열에서 arr[i]보다 크거나 같은 값의 위치에 arr[i]로 갱신
				//이분탐색 사용하면 O(ind)에서 O(log(ind))으로 감소 				
				for (int j = 0; j < ind; j++)
				{
					if (d[j] <= arr[i])
					{
						d[j] = arr[i];
						break;
					}
				}
			}
		}
	}

	cout << ind << endl; //d배열의 데이터 갯수 출력

	return 0;
}