Максимальная вариация подмассива
Я должен решить проблему, очень похожую на проблему максимального подмассива. Я должен найти самый большой подмассив, среднее значение которого больше k. Я думал, что следующий трюк. Я могу преобразовать мой массив A[] размера n в B[], где B[i] = A[i] - k. Так что теперь среднее значение должно быть>0. Но среднее больше нуля не означает просто сумму больше нуля? Так что я могу напрямую применить алгоритм Кадане. Я прав? (всегда с ограничением на 1 положительное значение)
2 ответа
Нет, алгоритм Кадане все равно найдет вам массив с наибольшей суммой... я должен решить ту же проблему. пока я нашел, что если мы создадим массив B, как вы упомянули выше, а затем создадим массив C, который содержит частичные суммы массива B, то максимальный интервал (i,j), который мы ищем, будет иметь то же число для меня и J!!! например:
массив A равен: 1 10 -1 -1 4 -1 7 2 8 1 ..... и заданное k равно 5, тогда массив B равен: -4 5 -6 -6 -1 -6 2 -3 3 -4 массив C имеет вид:-4 1 -5 -11 -12 -18 -16 -19 -16 -20, поэтому искомая матрица имеет вид [7,2,8], имеет длину 3 и имеет то же самое первое и последний элемент который -16!!!!
редактировать: я забыл сказать, что мы ищем алгоритм O(n) или O(n*logn).... @lets_solve_it вы правы, но ваш алгоритм O(n^2), что является большой путь для данные, которые мы хотим обработать. Я близок к решению этой проблемы с помощью карты функций в C++, которая похожа на хеш-таблицу. Мне кажется, это правильное направление, потому что здесь элементы массива C имеют прямую связь со своими индексами! Также наш профессор сказал нам, что еще одно возможное решение - это снова сделать массив C, а затем сделать (особый?) Поворот для быстрой сортировки... но я не совсем понимаю, что мы ожидаем от быстрой сортировки.
@ Panos7:
после того, как вы создали массив C (массив частичных сумм), вы ищете два значения C, Ci и Cj,
такой, что Cj>=Ci, и (ji) настолько "большой", насколько это возможно. (Джи) -> Макс.
тогда верни джи.
в вашем примере -16>=-18, так что вы вернули ji=9-6=3
это правильный ответ!