Leave Out All The Rest

• merge된 수열의 LIS의 길이의 최댓값은 {a의 LIS의 길이} + {b의 LIS의 길이}임은 자명하다
• 그리고, a의 LIS와 b의 LIS를 잘 merge 하면, 정렬된 상태의 수열을 얻을 수 있다. 즉, a와 b를 merge할때, a의 LIS와 b의 LIS가 정렬된 상태가 되도록 merge해주기만 하면, 머지된 수열의 LIS 길이가 {a의 LIS의 길이} + {b의 LIS의 길이}가 되도록 만들수 있다.
• 결국, 답은 {a의 LIS의 길이} + {b의 LIS의 길이}가 되고, 각각의 LIS를 구하는 O(nlogn + mlogm)이 총 시간복잡도가 된다.
• 만약, a와 b에 겹치는 원소들이 있고, 만들어야 하는 것이 strictly increasing subsequence 였다면 문제가 복잡해졌을텐데, 문제 조건에서 a와 b에 겹치는 원소들이 없다고 주어졌으므로 이것으로 충분히 풀린다.

"""Solution code for "BOJ 19086. Leave Out All The Rest".

- Problem link: https://www.acmicpc.net/problem/19086
- Solution link: http://www.teferi.net/ps/problems/boj/19086

Tags: [lis]
"""

from teflib import seqtask


def main():
    _n = int(input())
    a = [int(x) for x in input().split()]
    _m = int(input())
    b = [int(x) for x in input().split()]

    lis_len_a = seqtask.longest_inc_subseq_length(a)
    lis_len_b = seqtask.longest_inc_subseq_length(b)

    print(lis_len_a + lis_len_b)


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.longest_inc_subseq_length