@Rsa97, спасибо)
Кстати, не проходит по времени все-таки. Там кол-во элементов в последовательности может быть до 10^6. Так что, все-таки имеется у этой задачи менее грубое решение...
А для последовательности чисел, то есть, как вы изначально спрашивали, если подпоследовательности представляются, как массивы элементов, то как тогда делать?
@rEAcT1oNmanT1s,
Да, последовательность в вопросе - это пример.
Да, вы правы. Именно в повторяющихся цифрах загвоздка. Формулу для подсчета уникальных подпоследовательностей, при условии отсутсвия повторяющихся более двух раз цифр, я уже нашел.
Слишком медленно получится скорее всего.
А вы не могли бы код ближе к языку давать какому-нибудь? C++ например? А то псевдокод тяжело воспринимать.
Ваш вариант натолкнул меня на такую идею:
Можно вычислить кол-во уникальных последовательностей для отдельно взятой цифры только по ее позиции, используя формулу суммы членов арифметической прогрессии.
То-есть на позиции 1, будет ((n - 1) / 2) * n последовательностей, где n - длина исходной подпоследовательности.
Спасибо большое за ответ.
Если не сложно, вы не могли бы на примере небольшой последовательности (Допустим 8 2 4 6) показать использование этого метода?
Разве 2n-1 - это кол-во всех подпоследовательностей?
У меня такая формула получилась:
n - Кол-во последовательностей на шаге
l - Кол-во символов в последовательностях на шаге
n * l - кол-во последовательностей на след шаге
==>
Для 8 2 4 6:
1) 1 * 4 = 4
2) 4 * 3 = 12
3) 12 * 2 = 24
Сумма всех: 40
И прибавляем еще 1, потому что выше не учитывается исходная последовательность: 8246
Получаем 41 последовательность.
Но нужно узнать уникальных, а не всех.
Вообще, у меня стоит связка Apache + nginx, но так как я с nginx не работал вплотную никогда (Связка из коробки OpenServer'а стоит), то с трудом понимаю первую часть вашего ответа.
Кстати, не проходит по времени все-таки. Там кол-во элементов в последовательности может быть до 10^6. Так что, все-таки имеется у этой задачи менее грубое решение...
Но большое спасибо вам за помощь.