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

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

이 문제는 dp테이블 하나와 수열의 값을 담는 배열을
사용해야겠다고 접근했다.

#include <bits/stdc++.h>
using namespace std;

int N;
int seq[1002];
int dp[1002];

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	
	cin >> N;
	for(int i=1;i<=N;i++){
		cin >> seq[i];
	}
	for(int i=1;i<=N;i++){
		dp[i]=dp[0]+1;
		for(int j=1;j<i;j++){
			if(seq[i]>seq[j]){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
	}
	sort(dp,dp+1002);
	cout << dp[1001];
}

수열에 있는 어떤 한 값 seq[i] 보다 작은 인덱스들을 탐색하면서 seq[i]보다 작으면 dp테이블 dp[i]에 dp[j]+1을 해주었다.

이때 최대한 긴 수열을 만들어야 하므로 max함수를 이용해 최대 길이를 구해주었다.