각 인덱스마다 해당 인덱스까지의 최장 부분 수열 길이를 저장한다.
어떤 인덱스 i의 최장 부분 수열의 길이는 이전 인덱스 1∼i−1 중 가장 긴 최장 부분 수열 길이에 1을 더한 값이다. 또한 당연히 선택된 이전 부분 수열의 마지막 요소는 반드시 i번째 요소보다 작아야 한다.
최종 답을 구할 때, 답은 배열의 마지막 인덱스가 아니라 LIS 마지막 요소의 인덱스에 있으므로 모든 요소를 검사해 가장 긴 값을 찾아야 한다.
점화식
{ni=인덱스i로끝나는가장긴 LIS 길이ai=i번째수\begin{cases}
n_k &\text{\small{if $a_{i} > a_{k}$}} \\
0 &\text{\small{else}}
\end{cases}
) + 1} $$
^333d04
새로운 인덱스의 최장 부분 수열 길이를 계산하려면 이전의 모든 인덱스를 검사해야하므로 시간 복잡도는 $O(N^2)$이다.
#### 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n; vector<int> arr(n + 1), dp(n + 1, 1); // 모든 위치에서 최소 부분 수열 길이는 1임
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
int d = 1;
for (int i = 2; i <= n; i++) {
int mx = 0;
for (int j = 1; j < i; j++) {
if (arr[i] > arr[j]) { // 증가 수열인 경우
mx = mx > dp[j] ? mx : dp[j]; // 이전 값에서 가장 긴 LIS 탐색
}
}
dp[i] = mx + 1; // 이전의 가장 긴 증가 수열에 +1
d = d > dp[i] ? d : dp[i]; // 최장 수열은 1~n 어디서든 발생할 수 있다.
}
cout << d;
return 0;
}
```