Кухня(); Задание N66

public static void getPalindromeAndLength2(int... array) {
    int count = 1;
    int length = array.length;
    for (int i = 0; i < count; i++) {
        boolean isPalindrome = false;
        if((array.length - count + 1) == 1)
            isPalindrome = true;
        else
            for (int j = 0; j < (length - count + 1) / 2; j++) {
                if (array[i + j] == array[i + array.length - count - j]) {
                    if (j + 1 == (array.length - count + 1) / 2)
                        isPalindrome = true;
                } else
                    break;
            }
        if (isPalindrome) {
            int[] temp = Arrays.copyOfRange(array, i, array.length - count + i + 1);
            System.out.println(Arrays.toString(temp) + ", length = " + temp.length);
            return;
        }
        if(i + 1 == count) {
            i = 0;
            count++;
        }
    }
}

public static void solve(int[] arr) {
    int n = arr.length;
    int i1 = 0, i2 = 0;

    int leftPivot = 0;
    int rightPivot = 1;

    while (rightPivot < n) {
        for (int l = leftPivot, r = rightPivot; l >= 0 && r < n; l--, r++) {
            if (arr[l] != arr[r]) {
                break;
            }

            if (r - l > i2 - i1) {
                i1 = l;
                i2 = r;
            }
        }

        if (leftPivot + 1 == rightPivot) {
            rightPivot++;
        }
        else {
            leftPivot++;
        }
    }

    for (int i = i1; i <= i2; i++) {
        System.out.printf("%d ", arr[i]);
    }
    System.out.printf("\n%d", i2 - i1 + 1);
}

public static void solve(int[] arr) {
    int n = arr.length;

    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j + i < n; j++) {
            if (isPal(arr, j, j + i)) {
                print(arr, j, j + i);
                return;
            }
        }
    }

    System.out.println(arr[0]);
    System.out.println(1);
}

public static boolean isPal(int[] arr, int bg, int en) {
    if (en - bg < 1) {
        return true;
    }
    else if (en - bg < 3) {
        return arr[bg] == arr[en];
    }
    else {
        return arr[bg] == arr[en] && isPal(arr, bg + 1, en - 1);
    }
}

public static void print(int[] arr, int bg, int en) {
    for (int i = bg; i <= en; i++) {
        System.out.printf("%d ", arr[i]);
    }
    System.out.printf("\n%d", en - bg + 1);
}

public static void solve(int[] arr) {
    int n = arr.length;
    int offset = 0; // индекс первого элемента искомого палиндрома
    int count = 0; // offset + count = индекс последнего элемента искомого палиндрома

    // isPalindrome[o][c] является true, если подпоследовательность,
    // начиная с элемента o и заканчивая элементом o + c является палиндромом
    boolean[][] isPalindrome = new boolean[n][];
    for (int i = 0; i < n; i++) {
        // в массиве есть всего n - i подпоследовательностей,
        // начинающихся с i-го элемента данного массива
        isPalindrome[i] = new boolean[n - i];
        // подпоследовательность из одного элемента всегда палиндром
        isPalindrome[i][0] = true;
    }

    // рассмотрим все двухэлементные подпоследовательности
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] == arr[i + 1]) {
            isPalindrome[i][1] = true;
            if (count < 1) {
                offset = i;
                count = 1;
            }
        }
    }

    // и остальные подпоследовательности
    // c - count, o - offset
    for (int c = 2; c < n; c++) {
        for (int o = 0; o + c < n; o++) {
            // типа рекурсивная функция
            // isPal(arr, i, j) = arr[i] == arr[j] && isPal(arr, i + 1, j - 1)
            if (arr[o] == arr[o + c] && isPalindrome[o + 1][c - 2]) {
                isPalindrome[0][c] = true;
                if (c > count) {
                    offset = o;
                    count = c;
                }
            }
        }
    }

    // вывод с arr[offset] по arr[offset + count],
    // длина равна count + 1
    for (int i = offset; i <= offset + count; i++) {
        System.out.printf("%d ", arr[i]);
    }
    System.out.printf("\n%d\n", count + 1);
}