11053번 가장 긴 부분수열

문제 링크 : www.acmicpc.net/problem/11053

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

---

---

<알고리즘>

  : 각 수열의 요소를 돌면서 자신의 앞에 자신보다 작은 수가 몇개나 있는 지 확인해 dq에 기록한다.

    단, 이때 중복되는 숫자들이 있을 수 있으므로 숫자 자체를 비교하여 dq를 기록하기보단,

    숫자를 비교한 후 조건에 충족되면 indexd의 dq값끼리 비교하여 큰수를 dq에 재기록한다.

 

ex)

  주어진 예제

   6

   10 20 10 30 20 50 

 

  (1)arr[0]과 arr[0] 비교

arr	10	20	10	30	20	50
dq	1	1	1	1	1	1

  (2) arr[1]과 arr[0] 비교 -> 조건 충족하므로 dq[1]와 dq[0]+1(자신보다 큰수가 등장해서) 비교 후 수정

arr	10	20	10	30	20	50
dq	1	2	1	1	1	1

  (3) arr[2]와 arr[0],[1] 비교

arr	10	20	10	30	20	50
dq	1	2	1	1	1	1

  (4) arr[3]과 arr[0],[1],[2] -> 조건 충족하므로 dq[3]와 dq[1]+1(자신보다 큰수가 등장해서) 비교 후 수정

arr	10	20	10	30	20	50
dq	1	2	1	3	1	1

  (5) arr[4]와 arr[0],[1],[2],[3] > 조건 충족하므로 dq[4]와 dq[0],[2]+1(자신보다 큰수가 등장해서) 비교 후 수정

arr	10	20	10	30	20	50
dq	1	2	1	3	2	1

  (6) arr[5]와 arr[0],[1],[2],[3],[4] -> 조건 충족하므로 dq[5]와 dq[3]+1(자신보다 큰수가 등장해서) 비교 후 수정

arr	10	20	10	30	20	50
dq	1	2	1	3	2	4

 

 

 

 

메모리 : 2016MB   시간 : 0ms

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int N = 0;
	cin >> N;
	
	vector<int>sequence;
	int a = 0;
	for (int i = 0; i < N; i++) {
		cin >> a;
		sequence.push_back(a);
	}
	
	vector<int> dq(N, 1);
	int maximum = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (sequence[i] > sequence[j]) {
				dq[i] = max(dq[i], dq[j] + 1);
			}
		}
		maximum = ((dq[i] > maximum) ? dq[i] : maximum);
	}
	cout<<maximum<<"\n";
	return 0;
}