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

Поиск самой длинной подпоследовательности, сумма которой делится на 3 в С++
Описание: Для решения этой задачи мы можем использовать динамическое программирование. Создадим двумерный массив dp размером [n+1][3], где n - это количество чисел в последовательности, а 3 - возможные остатки суммы подпоследовательности при делении на 3 (0, 1 или 2).

Изначально все значения в массиве dp будут равны нулю. Затем мы будем заполнять массив, проходя по каждому числу в последовательности.

Для каждого числа a[i] мы будем выполнять следующие действия:
1. Скопируем значения из предыдущей строки dp[i-1] в текущую строку dp[i].
2. Используем формулу dp[i][(dp[i-1][k] + a[i]) % 3], где k принимает значения 0, 1 или 2. Обновим значение dp[i][(dp[i-1][k] + a[i]) % 3] путем прибавления 1 к dp[i-1][k].

После прохода по всей последовательности, длина наибольшей подпоследовательности, сумма которой делится на 3, будет храниться в dp[n][0].

Доп. материал:
Входные данные:
6
2
2
1
0
1
2

Решение:
dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = 0

dp[1][0] = 0
dp[1][1] = 0
dp[1][2] = 1

dp[2][0] = 0
dp[2][1] = 0
dp[2][2] = 2

dp[3][0] = 0
dp[3][1] = 1
dp[3][2] = 2

dp[4][0] = 1
dp[4][1] = 1
dp[4][2] = 2

dp[5][0] = 2
dp[5][1] = 2
dp[5][2] = 2

dp[6][0] = 2
dp[6][1] = 3
dp[6][2] = 3

Длина наибольшей подпоследовательности, сумма которой делится на 3, равна 3.

Совет: Для решения подобных задач по программированию важно разбить задачу на более простые этапы и создать план решения. В данном случае, использование динамического программирования позволяет пошагово заполнять массив и находить ответ.

Проверочное упражнение: Если входные данные изменились на следующие:

Входные данные:
5
0
0
2
2
1

Какое значение будет выведено на экран?