#arrays #algorithm #kadanes-algorithm
#массивы #алгоритм #алгоритм Каданеса
Вопрос:
Я получил онлайн-тестовую задачу, в которой они дали строку символов и значение для каждого символа. Значение каждого символа находится в диапазоне [-10, 10]. Проблема заключалась в том, чтобы найти подстроку, которая начинается и заканчивается одним и тем же символом и имеет максимальное значение. Проблема легко сводится к расширенной версии проблемы максимальной суммы подмассива после замены символов значениями. Ограничение заключается в том, что начальное и конечное значения будут одинаковыми. Я придумал наивное решение и был недостаточно хорош. Кто-нибудь может сказать мне, как решить это с помощью алгоритма Кадане или любого другого с лучшей временной сложностью?
Комментарии:
1. 1)
sum(a[i] .. a[j]) = sum(0 .. a[j]) - sum(0 .. a[i-1]). Таким образом, один O (n) проход предварительной обработки через массив упрощает вычисление любой суммы подмассива за O (1) время. 2) Вместо одного экземпляра алгоритма Кадане вы запускаете 26 экземпляров алгоритма Кадане (по одному на каждую букву). Общее время выполнения составляет O (n).
Ответ №1:
Этот вопрос предназначен для того, чтобы сделать алгоритм Кадане неподходящим.
Тем не менее, вы все еще можете сделать это быстро и легко:
-
Повторите последовательность, отслеживая совокупную сумму значений, предшествующих каждой букве.
-
Для каждой буквы запомните наименьшую предыдущую сумму, виденную до сих пор
-
Для каждой буквы последовательность максимальных значений, которая заканчивается там, начинается с экземпляра той же буквы с наименьшей предыдущей суммой, виденной до сих пор. Обратите внимание, что это может быть та же позиция для последовательности длиной 1.
-
Легко вычислить значение этой наилучшей последовательности, заканчивающейся на каждой букве: letter_value preceding_sum — smallest_preceding_sum_for_same_letter. Запомните самую ценную последовательность, которую вы найдете.