가장 긴 증가하는 부분 수열 4, 5

[fineman999]

14002번: 가장 긴 증가하는 부분 수열 4

[fineman999]

dp를 통해 이전 값이 작을 경우 dp[i] = max(dp[i], dp[j]+1)을 통해 해당 값을 업데이트 한다. x = MAX(dp) 그 후 뒤에서 부터 x 값이 dp[i] 째 값과 같을 경우 해당 값을 result에 저장 후 x-=1을 반복한다. 그 후 reverse() 후 출력

[fineman999]

14003번: 가장 긴 증가하는 부분 수열 5

[fineman999]

1. 기존 최대값보다 큰 값이 들어오면, dp에 추가하고 최장길이를 record에 기록한다.

2. 기존 최대값보다 작은 값이 들어오면, 그 값이 들어갈 중간 위치를 찾아서 동일한 dp를 가지는 값과 바꿔준다.

3. 최대 dp를 가지는 수부터 역으로 하나씩 담는다. 그 이후 reverse하여 출력

4. 더 작은 dp(LIS 길이)를 가지고, 더 작은 인덱스를 가지는 것들을 연결하여 담으면, 무조건 LIS가 완성된다.