Up and Down

• 가장 긴 바이토닉 부분 수열 과 같은 문제인데, 증가하는 구간과 감소하는 구간이 반드시 둘다 존재해야 한다는 점만 다르다. 기본 풀이는 가장 긴 바이토닉 부분 수열 를 참고하고, 여기에 증가하는 구간과 감소하는 구간이 존재하도록 확인하는 조건문만 추가해주면 된다
• 시간복잡도는 O(nlogn)

"""Solution code for "BOJ 32683. Up and Down".

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

Tags: [lis]
"""

import sys
from teflib import psutils
from teflib import seqtask


@psutils.run_n_times
def main():
    _N = int(sys.stdin.readline())
    a = [int(x) for x in sys.stdin.readline().split()]

    lis_lengths = seqtask.longest_inc_subseq_length_by_last_elem(a)
    lds_lengths = seqtask.longest_dec_subseq_length_by_first_elem(a)
    answer = 0
    for lis_len, lds_len in zip(lis_lengths, lds_lengths):
        if lis_len > 1 and lds_len > 1:
            answer = max(answer, lis_len + lds_len - 1)

    print(answer)


if __name__ == '__main__':
    main()

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