N,data = int(input()),[*map(int,input().split())]
result = 1
i = 0
while i < N-1:
if data[i] > data[i+1]:
i += 1
continue
if data[i] == data[i+1]:
result = max(result,2)
i += 1
continue
stack,l = [data[i]],1
while i<N-1 and data[i]<data[i+1]:
stack.append(data[i+1])
i += 1
if i<N-1 and data[i+1]==stack.pop():
l += 1
i += 1
while stack and i<N-1 and data[i+1]==stack.pop():
l += 2
i += 1
result = max(result,l)
print(result)
투 포인터 알고리즘으로 해결하였다.
핵심 포인트는 팰린드롬 부분수열이 증가하다가 감소해야하기 때문에, 감소하는 지점까지 탐색을 하고 나면 이전의 구간은 탐색할 필요가 없다는 것이다. 어차피 마지막 지점이 감소로 끝났기 때문에, 그 이후부터 탐색을 시작해야한다.
이를 토대로 설명하면,
1. i=0부터 탐색을 시작한다. 다음 값이 현재 값보다 작으면 continue, 같으면 2로 result로 갱신 후 continue 한다.
2. 다음 값이 현재 값보다 큰 경우, 증가가 유지될 때까지 stack에 숫자를 쌓아준다.
3. 증가가 멈추면, 만약 다음 값이 마지막 값과 같은 경우 팰린드롬 길이를 +1을 해주고 감소구간 탐색을 시작한다.
4. stack의 숫자들을 하나씩 pop 해주면서 다음 값과 비교한다. 같은 경우 팰린드롬 길이를 +2 해준다.
5. 같지 않은 경우 새로운 팰린드롬 탐색을 시작한다.
6. 가장 긴 길이를 출력한다.
오늘의 교훈) 다양한 팰린드롬 문제를 풀어보자