| 6 | int arr[1001]; |
| 7 | |
| 8 | int main(){ |
| 9 | ios::sync_with_stdio(0); |
| 10 | cin.tie(0); |
| 11 | int n, top = -1, top_i; |
| 12 | cin >> n; |
| 13 | dp[0] = 0; dp[0] = 0; |
| 14 | for(int i=1;i<=n;i++) cin >> arr[i]; |
| 15 | |
| 16 | for(int i=1;i<=n;i++) { |
| 17 | dp[i] = 1; |
| 18 | for(int j=1;j<=i;j++) { |
| 19 | if(arr[j] < arr[i] && dp[j] +1 > dp[i]) { |
| 20 | dp[i] = dp[j]+1; |
| 21 | } |
| 22 | |
| 23 | if(dp[i] > top) { |
| 24 | top = dp[i]; |
| 25 | top_i = i; |
| 26 | // LIS길이 최댓값을 갖는 인덱스를 top_i에 저장한다. |
| 27 | } |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | cout << top << '\n'; |
| 32 | |
| 33 | // 위에서 저장한 top_i 인덱스부터 시작해서 거꾸로 탐색하면 LIS를 구성하는 요소들을 출력할 수 있다. |
| 34 | for(int i=top_i;i>=1;i--) { |
| 35 | if(dp[i] == top) { |
| 36 | s.push(arr[i]); |
| 37 | top--; |
| 38 | } |
| 39 | } |
| 40 | |
| 41 | while(!s.empty()) { |
| 42 | cout << s.top() << ' '; |
| 43 | s.pop(); |
| 44 | } |
| 45 | } |