11722 가장 긴 감소하는 부분 수열

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MAX 1000
// 11722

int main(){
	int n;
	
	cin >> n;
	cin.ignore();
	
	vector<int> vec(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> vec[i];
	}
	
	vector<int> mem(n + 1, 1); // 해당 숫자로 끝나느 가장 긴 감소하는 길이를 저장 
	for(int i = 2; i <= n; i++){
		int maxMem = -1;
		for(int j = 1; j < i; j++){
			if(vec[j] <= vec[i]) continue;
			if(maxMem < mem[j]) {maxMem = mem[j];}
		}
		if(maxMem != -1) mem[i] = maxMem + 1;
	}
	
	int res = -1;
	for(int i = 1; i <= n; i++){
		if(res < mem[i]) res = mem[i];
	}
	
	cout << res << endl;

}

 

해설

이전의 2 문제. 11053, 11055 와 동일했다.