# JudgeGirl #32

## Longest Double Palindrome

For example `1 3 5 3 1` and `1 2 2 1` are both palindromes. To the extreme case `1` is also a palindrome.
We also define a double palindrome as the concatenation of two palindromes. For example `1 3 5 3 1 1 2 2 1` is a double palindrome.
To the extreme case `1 3 5 3 1 1` is also a double palindromes

## Keys

### 1. Define isPallind()
For each number in between, check every corresponding number on the opposite side. Until the corresponding num is self or behind. Return 0 if does not match

int isPalind(int h, int t) { // h = head, t = tail
    if (h == t) return 1; // extreme case (single number)
    int c = t - h - 1; // count of numbers in between
    for (int i = 1; i < c; i++) {
        if (t - i < h + i) break; // is behind
        if (a[h+i] != a[t-i]) return 0; // not match
    }
    return 1;
}

### 2. Remember every longest palindrome we've seen
We don't keep track of every palin because that's too many. Keep track of every longest one to save some space.
Save them into 2 arrays so that each pallin's `(start, end)` is `(heads[i], tail[i])`.

int heads[128], tails[128], count = 0;
for (int i = 0; i < c; i++) {
    for (int j = c - 1; j >= i; j--) {
        if (a[i] == a[j] && isPallind(i, j)) {
            heads[count] = i;
            tails[count] = j;
            count++;
            break;
        }
    }
}

### 3. Determine the longest palindrome
Loop through every palin `i` we've seen, and for each of them loop through every palin `j` from back of the array, check if the head of `j` is the tail + 1 of `i` (next to each other).
Update ans if length of current one is >= ans.
If `i` is the last one and there's no next one, `i` will be `i - 1` and `j` will be the last one.

int max = 0, ansi = 0, ansj = 0;
for (int i = 0; i < count - 1; i++) {
    int nexttail = tails[count - 1]; // default j
    for (int j = i + 1; j < count; j++) {
        // next to each other
        if (heads[j] == tails[i] + 1) nexttail = tails[j]; //
    }
    int thishead = heads[i];
    // when i is last and no next one
    if (nexttail == tails[i]) thishead = heads[i - 1];
    // update ans
    if (nexttail - thishead >= max) {
        max = nexttail - thishead;
        ansi = thishead;
        ansj = nexttail;
    }
}

## Code

#include <stdio.h>

int a[128];

int isPalind(int h, int t) {
    if (h == t) return 1;
    int c = t - h - 1; // count of numbers in between
    for (int i = 1; i < c; i++) {
        if (t - i < h + i) break;
        if (a[h+i] != a[t-i]) return 0;
    }
    return 1;
}

int main() {
    int c = 0;
    while (scanf("%d", &a[c]) != EOF) c++;

    int heads[128], tails[128], count = 0;
    for (int i = 0; i < c; i++) {
        for (int j = c - 1; j >= i; j--) {
            if (a[i] == a[j] && isPalind(i, j)) {
                heads[count] = i;
                tails[count] = j;
                count++;
                break;
            }
        }
    }

    int max = 0, ansi = 0, ansj = 0;
    for (int i = 0; i < count - 1; i++) {
        int nexttail = tails[count - 1];
        for (int j = i + 1; j < count; j++) {
            if (heads[j] == tails[i] + 1) nexttail = tails[j];
        }
        int thishead = heads[i];
        if (nexttail == tails[i]) thishead = heads[i - 1];
        if (nexttail - thishead >= max) {
            max = nexttail - thishead;
            ansi = thishead;
            ansj = nexttail;
        }
    }

    for (int i = ansi; i <= ansj; i++) printf("%d%c", a[i], " \n"[i==ansj]);

    return 0;
}