가장 긴 증가하는 팰린드롬 부분수열
면접 대비시간 제한1.5초메모리 제한512 MB
최대 10^5개의 정수에서 연속된 구간 중 양 끝에서 중앙으로 갈수록 값이 커지는 회문의 최대 길이를 구합니다.
문제
팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드롬이 아니다.
증가하는 팰린드롬 수열이란 원소들이 바깥에서 팰린드롬 중심으로 갈수록 값이 증가하는 팰린드롬 수열을 말한다. 수열 {1, 2, 3, 2, 1}, {32, 59, 75, 75, 59, 32}는 증가하는 팰린드롬이고, {3, 2, 1, 2, 3}, {32, 57, 57, 80, 57, 57, 32}, {8, 7, 9, 7, 8}은 증가하는 팰린드롬이 아니다.
주어지는 수열 S에서 인접한 원소들로 구성된 부분수열 중 길이가 가장 긴 증가하는 팰린드롬 부분수열의 길이를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 수열 S의 길이 N(1 ≤ N ≤ 105)이 주어진다.
둘째 줄에 수열 S의 i번째 원소를 의미하는 정수 Si(1 ≤ Si ≤ 109)가 순서대로 공백으로 구분되어 주어진다.
출력
수열 S에서 인접한 원소들로 구성된 부분수열 중 길이가 가장 긴 증가하는 팰린드롬 부분수열의 길이를 출력하라.