Как найти наиболее длинную подпоследовательность?

Question

Вводится массив целых чисел. Найти наиболее длинную подпоследовательность подряд идущих элементов, которые чередуются (реализовать функцию, которая будет возвращать позицию первого элемента такой подпоследовательности и кол-во элементов ). В случае нескольких таких подпоследовательностей вывести вторую по счету справа. Для массива { 4, 6, 1, 2, 1, 2, 3, 2, 3, 5, 4, 7, 4, 1, 5, 1, 5, 6} правильным ответом будет {2, 3, 2, 3}.

Получилось сделать алгоритм нахождения всех подходящих по условию подпоследовательностей минимальной длинны (длинной четыре элемента, например 1,2,1,2),индекс(но кажется неправильно) и номер, но как находить те которые больше минимальной длинны и максимальную из них.

import org.apache.commons.lang3.ArrayUtils;

public class Task7 {
    public static void main(String[] args){
        int[] arr = new int[] { 4, 6, 1, 2, 1, 2, 3, 2, 3, 5, 4, 7, 4, 1, 5, 1, 5, 6};
        isTrueSeq(arr);
    }
    public static double isTrueSeq(int[] mainArray){
        for(int i = 0;i<=mainArray.length;i++){
            if((mainArray[0+i] == mainArray[2+i]) && (mainArray[1+i] == mainArray[3+i]) ){
                int indx = ArrayUtils.indexOf(mainArray, mainArray[0+i] );

                int[] newArr = new int[]{mainArray[0+i],mainArray[1+i],mainArray[2+i],mainArray[3+i]};
                int ColVo = newArr.length;

                System.out.println(
                        java.util.Arrays.toString(newArr) +
                                " Индекс 1-го элемента=" + indx +
                                " Количество элементов=" + ColVo);
            }
        }
        return 0;
    }
}

Вывод:
[1, 2, 1, 2] Индекс 1-го элемента=2 Количество элементов=4
[2, 3, 2, 3] Индекс 1-го элемента=3 Количество элементов=4
[1, 5, 1, 5] Индекс 1-го элемента=2 Количество элементов=4

Answer 1

public class Main {
static int sequenceLengthTmpC = 0;
static int sequenceLengthResC = 0;
static int indexTmpC = 0;
static int indexResC = 0;
static boolean flag2 = false;

public static boolean check(int next, int previous) {
    return next == previous;
}

public static void checkSeq() {
    if (sequenceLengthTmpC > sequenceLengthResC || (flag2 && sequenceLengthTmpC == sequenceLengthResC)) {
        flag2 = sequenceLengthResC != sequenceLengthTmpC;
        sequenceLengthResC = sequenceLengthTmpC;
        sequenceLengthTmpC = 0;
        indexResC = indexTmpC;
    } else {
        sequenceLengthTmpC = 0;
    }
}

public static void solution() {
    int[] arr = ru.vsu.cs.util.ArrayUtils.readIntArrayFromConsole();
    boolean flag1 = true;
    for (int i = 1; i < arr.length - 1; i++) {
        if (check(arr[i - 1], arr[i + 1])) {
            if (flag1) {
                indexTmpC = i - 1;
                flag1 = false;
                sequenceLengthTmpC += 3;
            } else {
                sequenceLengthTmpC++;
            }
        } else {
            flag1 = true;
            checkSeq();
        }
    }
    checkSeq();
}

Если будут какие-либо вопросы по коду обращайтесь.

Answer 2

Обозначим через f_n длину самой длинной чередующейся последовательности, которая оканчивается на n-ном символе строки s.

Между f_n-1 и f_n можно заметить связь:

если f_n-1 ≥ 2 и s_n = s_n-2, то f_n = f_n-1 + 1;

если f_n-1 ≥ 2 и s_n ≠ s_n-2 и s_n ≠ s_n-1 то f_n = 2;

если f_n-1 ≥ 2 и s_n ≠ s_n-2 и s_n = s_n-1 то f_n = 1;

если f_n-1 = 1 и s_n ≠ s_n-1 то f_n = 2;

если f_n-1 = 1 и s_n = s_n-1 то f_n = 1.

То есть f_n полностью определяется f_n-1, s_n, s_n-1 и s_n-2. Алгоритм будет обрабатывать числа последовательно, хранить целиком массив не нужно.

import java.util.Scanner;

public class Task7 {
    public static void main(String... args) {
        int index = 0;
        int prev_value = 0;
        int prev_prev_value = 0;
        int start = 0;
        int max_length_so_far = 0;
        int prev_start = 0;
        int prev_max_length_so_far = 0;
        int max_length_ending_here = 0;

        Scanner s = new Scanner(System.in);
        while (s.hasNextInt()) {
            final int value = s.nextInt();
            if (max_length_ending_here == 0) {
                max_length_ending_here = 1;
            } else if (max_length_ending_here == 1) {
                if (value != prev_value) {
                    max_length_ending_here = 2;
                }
            } else {
                if (value == prev_prev_value) {
                    ++max_length_ending_here;
                } else if (value == prev_value) {
                    max_length_ending_here = 1;
                } else {
                    max_length_ending_here = 2;
                }
            }

            if (max_length_ending_here >= max_length_so_far) {
                prev_start = start;
                prev_max_length_so_far = max_length_so_far;
                max_length_so_far = max_length_ending_here;
                start = index - max_length_ending_here + 1;
            }

            prev_prev_value = prev_value;
            prev_value = value;
            ++index;
        }

        if (prev_max_length_so_far == max_length_so_far) {
            start = prev_start;
        }
        System.out.println(start + " " + max_length_so_far);
    }
}

$ javac Task7.java

$ echo 4 6 1 2 1 2 3 2 3 5 4 7 4 1 5 1 5 6 | java Task7
5 4

БЛОГ НА HUSL

Как найти наиболее длинную подпоследовательность?

Ответы (2 шт):