93. 최대 부분 증가수열 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include <iostream>

using namespace std;

int a[1000];
int dy[1000];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m = 0, res = 0;
	cin >> n;
	
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	
	dy[1] = 1;
	
	for(int i = 2; i <= n; i++)
	{
		int max = 0;
		for(int j = i-1; j >= 1; j--)
		{
			if(a[j] < a[i] && dy[j] > max)
				max = dy[j];
		}
		dy[i] = max + 1;
		if(dy[i] > res) res = dy[i];
	}
	
	cout << res << "\n";	
	
	return 0;
}

1. 입력이 아래와 같이 들어온다.

5

3

7

8

6

2

9

4

2. 5로 만들 수 있는 수열은 5 하나 뿐이다. (dy[1] = 1)

3. 5와 3으로 만들 수 있는 증가수열은 3 하나다.

4. 5,3,7로 만들 수 있는 증가수열은 (5,7), (3,7)이다.

• dy[1~2] 까지 중 제일 큰 값 dy[1] + 1 을 dy[3]에 대입

5. 5,3,7,8로 만들 수 있는 증가수열은 (5,8), (3,8), (5,7,8), (3,7,8) 이다.

• dy[1~3] 까지 중 제일 큰 값 dy[3] + 1 을 dy[4]에 대입

 

... 반복