[동적 계획법] JLIS

[1. 문제 재정의 및 추상화]

1.  

 

[2. 해결 계획]

• 두 수열의 LIS 를 찾은 뒤 각각 합치면 해결 할 수 없다
• LIS 를 구하는 재귀 함수의 입력을 두개로 늘려야 함
  => 각 수열을 받기 위해
  => A[indexA] 와 B[indexB] 에서 시작하는 합친 증가 부분 수열의 최대 길이를 구하는 함수
• A[indexA] 와 B[indexB] 중 작은 쪽이 앞에 온다고 가정
• 이 증가 부분 수열의 다음 숫자는 두가지 경우가 존재
  1. A[indexA +1] 이후 또는
  2. B[indexA +1] 이후 수열 중 
  max(A[indexA], B[indexB]) 보다 큰 수 중 하나
  => 증가 부분 수열이 되기 위해선 A[indexA], B[indexB] 보다 큰 값이 뒤에 와야 한다.

 

[3. 계획 검증]

•