Максимальная вариация подмассива

нет, алгоритм Кадане все равно найдет подмассив с наибольшей суммой... мне нужно решить ту же проблему. до сих пор я обнаружил, что если мы создадим массив 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, а затем использовать (специальный?) Свод для быстрой сортировки... но я не совсем понимаю, что мы ожидаем от быстрой сортировки.

@panos7:

после того, как вы создали массив C (массив частичных сумм), вы ищете два значения C, Ci и Cj,

такое, что Cj>=Ci, и (j-i) является настолько «большим», насколько это возможно. (j-i) --> МАКС.

затем вернуть j-i.

в вашем примере -16>=-18, поэтому вы вернули j-i=9-6=3

какой правильный ответ!