[CH08] JLIS

[wbluke]

https://algospot.com/judge/problem/read/JLIS

APSS_p236

[wbluke]

[My Point]

• 두 LIS를 구해서 합쳐보려고 했는데, 불가능하다는 것을 깨달았다. 합치면 다른 최적해가 나올 수 있기 때문.

[Idea Point]

• findJLIS(indexA, indexB) 로 받아서 다음 인덱스의 재귀 호출을 생각해본다.
• 입력이 32비트 부호 있는 정수의 모든 값이므로 최소 비교값으로 64비트 정수형을 둔다.

[New Things]

• const type NEGINF = numeric_limits::min(); : 해당 type의 최소치(최대치)를 얻을 수 있다.

[wbluke]

[Idea Point]

• A[indexA] 와 B[indexB] 중 더 큰 수를 찾는다. 그 수를 기준으로 다음 수를 찾아내는 알고리즘을 작성한다. index가 -1이라면 NEGINF를, 아니면 해당 인덱스 원소를 넣어준다. 자료형에 신경쓰기!