• 바이토닉 부분 수열에서 가장 큰 수를 S[i] 로 고정시킨다면, 가장 긴 바이토닉 부분 수열은, S[i]로 끝나는 LIS와 S[i]로 시작하는 LDS를 합쳐놓은 것이 된다.
• 모든 i에 대해서 S[i]로 끝나는 LIS와 S[i]로 시작하는 LDS를 O(nlogn)에 구해둔 뒤에, 가장 큰 수가 S[i]인 가장 긴 바이토닉 부분 수열들 중에서 가장 긴 것을 O(n)에 찾으면 된다.
• 총 시간복잡도는 O(nlogn)

"""Solution code for "BOJ 11054. 가장 긴 바이토닉 부분 수열".

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

Tags: [LIS]
"""

from teflib import seqtask


def main():
    _N = int(input())
    A = [int(x) for x in input().split()]

    lis_lengths = seqtask.longest_inc_subseq_length_by_last_elem(A)
    lds_lengths = seqtask.longest_dec_subseq_length_by_first_elem(A)
    print(max(l1 + l2 for l1, l2 in zip(lis_lengths, lds_lengths)) - 1)


if __name__ == '__main__':
    main()

• Dependency
  • teflib.seqtask.longest_inc_subseq_length_by_last_elem
  • teflib.seqtask.longest_dec_subseq_length_by_first_elem