Незнайка, знающий язык программирования C ++, хочет найти наибольшую подпоследовательность из данной последовательности

Vesna

42

Хорошо, давайте начнем с решения данной задачи.

Для начала, нам потребуется программировать на языке C++. Программа должна считывать последовательность целых чисел с клавиатуры. Затем, мы должны вычислить длину самой длинной подпоследовательности, сумма элементов которой кратна 3. И, наконец, вывести результат на экран.

Давайте разобьем задачу на несколько шагов для более простого решения:

1. Считывание последовательности целых чисел с клавиатуры:
- Мы начинаем с объявления переменных. Нам понадобятся переменная `n`, которая будет содержать количество элементов, и массив `sequence`, где мы будем хранить сами элементы последовательности.
- Затем считываем значение `n` с клавиатуры.
- Создаем цикл `for`, чтобы считать элементы последовательности и сохранить их в массиве `sequence`.

2. Вычисление длины самой длинной подпоследовательности, сумма элементов которой кратна 3:
- Мы будем использовать двумерный массив `dp`, где `dp[i][j]` будет содержать длину самой длинной подпоследовательности суммы `j`, используя элементы до `i`-го индекса в массиве `sequence`.
- Мы начинаем с задания базового случая, `dp[0][0] = 0`, так как длина подпоследовательности без элементов равна 0.
- Затем создаем два цикла `for`, чтобы заполнить массив `dp`.
- Внешний цикл будет идти по элементам последовательности (от 1 до `n`), а внутренний цикл будет идти от 0 до 2, так как сумма элементов может быть 0, 1 или 2 по модулю 3.
- Внутри цикла мы проверяем, можно ли добавить текущий элемент в подпоследовательность, чтобы получить сумму, равную `j`. Если это так, то обновляем значение `dp[i][j]` иначе оставляем его равным предыдущему элементу `dp[i-1][j]`.

3. Вывод результата на экран:
- После заполнения массива `dp`, мы просто находим максимальное значение в последней строке `dp[n]` и выводим его на экран.

Вот и всё! Теперь давайте перейдем к написанию кода на языке C++.

cpp

#include 

#include 

#include 



int main() {

    int n;

    std::cin >> n;

    

    std::vector sequence(n);

    

    for (int i = 0; i < n; i++) {

        std::cin >> sequence[i];

    }

    

    std::vector> dp(n+1, std::vector(3, 0));

    

    for (int i = 1; i <= n; i++) {

        for (int j = 0; j < 3; j++) {

            dp[i][j] = dp[i-1][j];

        }

        

        dp[i][sequence[i-1] % 3] = std::max(dp[i][sequence[i-1] % 3], dp[i-1][sequence[i-1] % 3] + 1);

    }

    

    int maxLength = *std::max_element(dp[n].begin(), dp[n].end());

    

    std::cout << maxLength;

    

    return 0;

}

Надеюсь, данное решение помогло вам понять, как создать программу для решения данной задачи. Если у вас возникнут дополнительные вопросы, не стесняйтесь задавать!