Наибольшая возрастающая последовательность на отрезке

@ThePonyCoder · Регистрация: 27.12.2017

Author24 — интернет-сервис помощи студентам

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

@Massaraksh7 · 17.01.2018, 23:44

Сообщение от ThePonyCoder

Поисков нвп нужно выполнить тоже около 200 тысяч раз.

Зачем? Можете озвучить всю задачу?

@Shamil1 · 18.01.2018, 00:08

Сообщение от ThePonyCoder

В общем нужно реализовать структуру для поиска наибольшей возрастающей подпоследовательности на отрезке. Количество чисел в массиве около 200 тысяч. Поисков нвп нужно выполнить тоже около 200 тысяч раз.

Дерево Фенвика проще.

@ThePonyCoder · 18.01.2018, 15:16 **[ТС]**

Пример:
Есть массив {1,2,5,12,10,16,7}
Задаём границы отрезков.
L1 = 1. R1 = 3
Макс НВП здесь будет {1,2,5}
L2 = 5. R2 = 7
НВП{10,16}
L3 = 4. R2 = 7
НВП{10,16}

@Shamil1 · 18.01.2018, 15:58

Почему не хотите использовать один из стандартных алгоритмов для нахождения НВП?

@ThePonyCoder · 19.01.2018, 17:28 **[ТС]**

Сообщение от Shamil1

Почему не хотите использовать один из стандартных алгоритмов для нахождения НВП?

А разве он не будет в этом случае слишком медленным?
Мне казалось есть что-то оптимальнее

@Shamil1 · 19.01.2018, 18:23

N logn, где N - длина отрезка, а n - длина НВП на этом отрезке.

@ThePonyCoder 0 / 0 / 0 Регистрация: 27.12.2017 Сообщений: 4
		1
	Наибольшая возрастающая последовательность на отрезке 17.01.2018, 22:01. Показов 2841. Ответов 6 Метки дерево отрезков, нвп (Все метки) В общем нужно реализовать структуру для поиска наибольшей возрастающей подпоследовательности на отрезке. Количество чисел в массиве около 200 тысяч. Поисков нвп нужно выполнить тоже около 200 тысяч раз. Поглядываю на дерево отрезков, но как не пытаюсь, никак не получается реализовать вообще. 0

@Massaraksh7 Айлурофил 441 / 375 / 107 Регистрация: 27.05.2017 Сообщений: 2,155 Записей в блоге: 1
	17.01.2018, 23:44	2
	Сообщение от ThePonyCoder Поисков нвп нужно выполнить тоже около 200 тысяч раз. Зачем? Можете озвучить всю задачу? 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	18.01.2018, 00:08	3
	Сообщение от ThePonyCoder В общем нужно реализовать структуру для поиска наибольшей возрастающей подпоследовательности на отрезке. Количество чисел в массиве около 200 тысяч. Поисков нвп нужно выполнить тоже около 200 тысяч раз. Дерево Фенвика проще. 0

@ThePonyCoder 0 / 0 / 0 Регистрация: 27.12.2017 Сообщений: 4
	18.01.2018, 15:16 [ТС]	4
	Пример: Есть массив {1,2,5,12,10,16,7} Задаём границы отрезков. L1 = 1. R1 = 3 Макс НВП здесь будет {1,2,5} L2 = 5. R2 = 7 НВП{10,16} L3 = 4. R2 = 7 НВП{10,16} 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	18.01.2018, 15:58	5
	Почему не хотите использовать один из стандартных алгоритмов для нахождения НВП? 0

@ThePonyCoder 0 / 0 / 0 Регистрация: 27.12.2017 Сообщений: 4
	19.01.2018, 17:28 [ТС]	6
	Сообщение от Shamil1 Почему не хотите использовать один из стандартных алгоритмов для нахождения НВП? А разве он не будет в этом случае слишком медленным? Мне казалось есть что-то оптимальнее 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	19.01.2018, 18:23	7
	N logn, где N - длина отрезка, а n - длина НВП на этом отрезке. 0