Подсчитайте различные последовательности, полученные заменой всех элементов подмассивов, имеющих одинаковые первый и последний элементы, на первый элемент любое количество раз

Учитывая массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти количество различных последовательностей, которые могут быть сформированы после выполнения приведенной ниже операции над данным массивом arr[] любое количество раз.

Choose two indices i and j such that arr[i] is equal to arr[j] and update all the elements in the range [i, j] in the array to arr[i].

Примеры:

Input: arr[] = {1, 2, 1, 2, 2}
Output: 3
Explanation:
There can be three possible sequences:

1. The initial array {1, 2, 1, 2, 2}.
2. Choose indices 0 and 2 and as arr[0](= 1) and arr[2](= 1) are equal and update the array elements arr[] over the range [0, 2] to arr[0](= 1). The new sequence obtained is {1, 1, 1, 2, 2}.
3. Choose indices 1 and 3 and as arr[1](= 2) and arr[3](= 2) are equal and update the array elements arr[] over the range [1, 3] to arr[1](= 2). The new sequence obtained is {1, 2, 2, 2, 2}.

Therefore, the total number of sequences formed is 3.

Input: arr[] = {4, 2, 5, 4, 2, 4}
Output: 5

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

• Инициализируйте вспомогательный массив dp[] , где dp[i] хранит количество различных последовательностей, возможных для первых i элементов данного массива arr[] и инициализируйте dp[0] как 1 .
• Инициализируйте массив lastOccur[] , где lastOccur[i] хранит последнее вхождение элемента arr[i] в первых i элементах массива arr[] и инициализируйте lastOccur[0] значением -1 .
• Переберите диапазон [1, N], используя переменную i , и выполните следующие шаги:
  • Обновите значение dp[i] как dp[i – 1] .
  • Если последнее вхождение текущего элемента не равно -1 и меньше (i – 1) , то добавьте значение dp[lastOccur[curEle]] к dp[i] .
  • Обновите значение lastOccur[curEle] как i .
• После выполнения вышеуказанных шагов выведите в качестве результата значение dp[N] .

Ниже приведена реализация вышеуказанного подхода:

Выход:

3

Временная сложность: O(N)
Вспомогательное пространство: O(N)