Three Blocks Palindrome (easy version) (Codeforces 1335E1)
Tags: DP, two pointers

The only difference between easy and hard versions is constraints.You are given a sequence $$$a$$$ consisting of $$$n$$$ positive integers.Let's define a three blocks palindrome as the sequence, consisting of at most two distinct elements (let these elements are $$$a$$$ and $$$b$$$, $$$a$$$ can be equal $$$b$$$) and is as follows: $$$[\underbrace{a, a, \dots, a}_{x}, \underbrace{b, b, \dots, b}_{y}, \underbrace{a, a, \dots, a}_{x}]$$$. There $$$x, y$$$ are integers greater than or equal to $$$0$$$. For example, sequences $$$[]$$$, $$$[2]$$$, $$$[1, 1]$$$, $$$[1, 2, 1]$$$, $$$[1, 2, 2, 1]$$$ and $$$[1, 1, 2, 1, 1]$$$ are three block palindromes but $$$[1, 2, 3, 2, 1]$$$, $$$[1, 2, 1, 2, 1]$$$ and $$$[1, 2]$$$ are not.Your task is to choose the maximum by length subsequence of $$$a$$$ that is a three blocks palindrome.You have to answer $$$t$$$ independent test cases.Recall that the sequence $$$t$$$ is a a subsequence of the sequence $$$s$$$ if $$$t$$$ can be derived from $$$s$$$ by removing zero or more elements without changing the order of the remaining elements. For example, if $$$s=[1, 2, 1, 3, 1, 2, 1]$$$, then possible subsequences are: $$$[1, 1, 1, 1]$$$, $$$[3]$$$ and $$$[1, 2, 1, 3, 1, 2, 1]$$$, but not $$$[3, 2, 3]$$$ and $$$[1, 1, 1, 1, 2]$$$.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the length of $$$a$$$. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 26$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$. Note that the maximum value of $$$a_i$$$ can be up to $$$26$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$ ($$$\sum n \le 2000$$$).

Output: For each test case, print the answer — the maximum possible length of some subsequence of $$$a$$$ that is a three blocks palindrome.


Sample Inputs:
6
8
1 1 2 2 3 2 1 1
3
1 3 3
4
1 10 10 1
1
26
2
2 1
3
1 1 1

Sample Outputs:
7
2
4
1
1
3

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    count = [0 for _ in range(27)]
    for i in l:
        count[i] += 1
    ans = 1
    for x in set(l):
        r = count[:]
        i = 0
        j = n - 1
        a = 2
        while i < j:
            while i < n and l[i] != x:
                r[l[i]] -= 1
                i += 1
            while j >= 0 and l[j] != x:
                r[l[j]] -= 1
                j -= 1
            if i >= j:
                break
            else:
                r[l[i]] -= 1
                r[l[j]] -= 1
                ans = max(ans, max(r) + a)
                a += 2
                i += 1
                j -= 1
    print(ans)

Solution (Python):
def main(read_in):
    out_list = []
    for read_one in read_in:
        out = 1
        num_map = {}
        for i in range(len(read_one)):
            num_map.setdefault(read_one[i], []).append(i)
        for x in num_map.keys():
            x_value = num_map[x]
            length = len(x_value)
            if length > out:
                out = length
            if length < 2:
                continue
            if x_value[-1] - x_value[0] < out:
                continue
            for y in num_map.keys():
                if y == x:
                    continue
                y_value = num_map[y]
                if y_value[-1] < x_value[0] or y_value[0] > x_value[-1]:
                    continue
                j_begin = 0
                j_end = len(y_value) - 1
                b = max((out - len(y_value)) // 2, 0)
                for i in range(b, length // 2):
                    x_begin = x_value[i]
                    x_end = x_value[-i - 1]
                    for j in range(j_begin, j_end + 1):
                        if y_value[j] > x_begin:
                            break
                        j_begin = j + 1
                    for j in range(j_end, j_begin - 1, -1):
                        if y_value[j] < x_end:
                            break
                        j_end = j - 1
                    if j_end < j_begin:
                        break
                    x_y_x = (i + 1) * 2 + (j_end - j_begin + 1)
                    if x_y_x > out:
                        out = x_y_x
        out_list.append(out)
    return out_list

def read_lines_input():
    read_in = []
    n = int(input())
    for i in range(n):
        s = input()
        s = input()
        read_one_line = [int(i) for i in s.split()]
        read_in.append(read_one_line)
    return read_in

def print_list(out_list):
    [print(s) for s in out_list]
''
if __name__ == '__main__':
    read_in = read_lines_input()
    out_list = main(read_in)
    print_list(out_list)

Solution (Python):
import time

def main(read_in):
    out_list = []
    b = time.time()
    for read_one in read_in:
        all_length = len(read_one)
        num_map = {}
        for i in range(all_length):
            num_map.setdefault(read_one[i], []).append(i)
        sort_num_map = {}
        for i in num_map.keys():
            tmp = sort_num_map.setdefault(len(num_map[i]), {})
            tmp[i] = num_map[i]
        out = max(sort_num_map.keys())
        num_map = {}
        for i in range(out, min(sort_num_map.keys()) - 1, -1):
            v = sort_num_map.setdefault(i, {})
            for j in v.keys():
                num_map[j] = v[j]
        for x in num_map.keys():
            if time.time() - b > 1.7:
                break
            x_value = num_map[x]
            x_length = len(x_value)
            if x_length < 2:
                break
            if x_value[-1] - x_value[0] < out:
                continue
            for y in num_map.keys():
                if y == x:
                    continue
                y_value = num_map[y]
                if y_value[-1] < x_value[0] or y_value[0] > x_value[-1]:
                    continue
                y_length = len(y_value)
                y_index = 0
                y_index_r = y_length - 1
                all_value = x_value + y_value
                all_value.sort()
                all_value_r = all_value[::-1]
                all_length = len(all_value)
                all_index = 0
                all_index_r = 0
                sum = y_length + 2
                while all_index < all_length - all_index_r and y_index <= y_index_r:
                    c_value = all_value[all_index]
                    all_index += 1
                    if c_value == y_value[y_index]:
                        sum -= 1
                        y_index += 1
                    else:
                        break
                while all_index_r < all_length - all_index and y_index <= y_index_r:
                    c_value = all_value_r[all_index_r]
                    all_index_r += 1
                    if c_value == y_value[y_index_r]:
                        sum -= 1
                        y_index_r -= 1
                    else:
                        break
                if y_index > y_index_r:
                    continue
                if sum > out:
                    out = sum
                for x_i in range(1, x_length // 2):
                    sum += 2
                    while all_index < all_length - all_index_r and y_index <= y_index_r:
                        c_value = all_value[all_index]
                        all_index += 1
                        if c_value == y_value[y_index]:
                            sum -= 1
                            y_index += 1
                        else:
                            break
                    while all_index_r < all_length - all_index and y_index <= y_index_r:
                        c_value = all_value_r[all_index_r]
                        all_index_r += 1
                        if c_value == y_value[y_index_r]:
                            sum -= 1
                            y_index_r -= 1
                        else:
                            break
                    if y_index > y_index_r:
                        break
                    if sum > out:
                        out = sum
        out_list.append(out)
    return out_list

def read_lines_input():
    read_in = []
    n = int(input())
    for i in range(n):
        s = input()
        s = input()
        read_one_line = [int(i) for i in s.split()]
        read_in.append(read_one_line)
    return read_in

def print_list(out_list):
    [print(s) for s in out_list]
''
if __name__ == '__main__':
    read_in = read_lines_input()
    out_list = main(read_in)
    print_list(out_list)