Note: Longest Increasing Subsequence #6
Description
가장 긴 증가하는 부분 수열 구하기 - 다이나믹 프로그래밍
D[i] = arr[i]를 마지막 원소로 가지는 부분 수열의 최대 길이- DP 테이블의 값은 모두 1로 초기화한다.
- 모든
0 <= j < i에 대하여,D[i] = max(D[i], D[j] + 1)ifarr[j] < arr[i]
{{ message }}
D[i] = arr[i]를 마지막 원소로 가지는 부분 수열의 최대 길이0 <= j < i 에 대하여, D[i] = max(D[i], D[j] + 1) if arr[j] < arr[i]