[C++/Python] 백준 11053 - 가장 긴 증가하는 부분 수열

문제 링크

https://www.acmicpc.net/problem/11053

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

 

현재 값이 이전 값보다 크고 현재의 카운트가 이전의 카운트보다 작으면

현재의 카운트는 이전의 카운트+1 이 됩니다.

 

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	const int MAX = 1001;
	int dp[MAX];
	int cnt[MAX];
	int main(){
	fastio;
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	cin >> dp[i];
	int max_cnt = 0;
	for(int i=1;i<=n;i++){
	for(int j=1;j<i;j++){
	if(dp[i] > dp[j] && cnt[i] < cnt[j]){
	cnt[i] = cnt[j];
	}
	}
	max_cnt = max(max_cnt, ++cnt[i]);
	}
	cout << max_cnt << endl;
	return 0;
	}

view raw 11053.cpp hosted with ❤ by GitHub

	n = int(input())
	a = list(map(int, input().split()))
	dp = [0 for i in range(n)]
	for i in range(n):
	for j in range(i):
	if a[i] > a[j] and dp[i] < dp[j]:
	dp[i] = dp[j]
	dp[i] += 1
	print(max(dp))

view raw 11053.py hosted with ❤ by GitHub