https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
dp [i] : 해당 숫자를 포함한 가장 긴 증가하는 부분 수열의 길이
제일 작은 숫자일 수 있으므로 1로 설정
앞에 있는 친구들을 보며 나보다 숫자가 작고 dp [j]가 같거나 크면 dp [j]+1로 갱신
정답은 0~n-1까지 중에 max 끝 값이 아님
옛날엔 재귀로 짜서 좀 헤맸던 기억이 있다.