Второй алгоритм (6) решения задачи о максимальной подпоследовательности
Листинг 8.3. Второй алгоритм (6) решения задачи о максимальной подпоследовательности
cumarr[-l] = О for i = [0. n)
cumarr[i] = cumarr[i-l] + x[i] maxsofar = 0 for i = [0, n) for j = [i . n)
sum = cumarr[j] - cumarr[i-l]
/* sum - сумма x[i . . j ] */ maxsofar = max(maxsofar. sum)
(В задаче 5 рассматривается проблема доступа к cumarr[-l].) Этот код требует 0(п2) операций; анализ проводится так же, как и для алгоритма 2а.
Рассмотренные три варианта алгоритмов исследуют все возможные пары начального и конечного индексов, вычисляя сумму элементов последовательности. Поскольку таких последовательностей 0(п ), ни один алгоритм, проверяющий их все, не может быть быстрее квадратичного. Можете ли вы придумать способ обойти проблему и получить более быстрый алгоритм?
Главная
Каталог файлов
