Longest Increasing Palindromic Subsequence
InterviewTime limit1.5sMemory limit512 MB
Given up to 10^5 integers, find the longest contiguous subarray that is a palindrome whose values strictly rise from both ends toward the center.
- Level
Medium5 of 10
- Topics
- String, Two pointers, Array
- Solved
- No attempts yet
Problem
A palindromic sequence is a sequence that reads the same forwards and backwards. The sequences {13, 25, 3, 25, 13} and {9, 5, 5, 9} are palindromes, while {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, and {1, 1, 3, 2, 4} are not.
An increasing palindromic sequence is a palindromic sequence whose values increase as you move from the outside toward the center of the palindrome. The sequences {1, 2, 3, 2, 1} and {32, 59, 75, 75, 59, 32} are increasing palindromes, while {3, 2, 1, 2, 3}, {32, 57, 57, 80, 57, 57, 32}, and {8, 7, 9, 7, 8} are not.
Given a sequence S, write a program that prints the length of the longest increasing palindromic subsequence among the subsequences made up of adjacent elements of S.
Input
The first line gives the length N of the sequence S (1 ≤ N ≤ 105).
The second line gives the integers Si (1 ≤ Si ≤ 109), the i-th element of the sequence S, in order, separated by spaces.
Output
Print the length of the longest increasing palindromic subsequence among the subsequences made up of adjacent elements of S.