Максимальный подмассив

Question

В графе 8 "Программирование жемчужин". Существует максимальная проблема подмассива.

Проблема:

Входные данные представляют собой вектор x из n чисел с плавающей точкой; выход - максимальная сумма, найденная в любом смежном подвекторе ввода. Чтобы завершить определение задачи, скажем, что когда все входные данные отрицательны, максимальный суммарный субвектор является пустым вектором с нулевой суммой.

Наиболее эффективное решение:

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    maxendinghere = max(maxendinghere+x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

В этом столбце есть упражнение: мы определили максимальный подвектор массива отрицательных чисел равным нулю, сумму пустого подвектора. Предположим, что вместо этого мы определили максимальный подвектор как значение самого большого элемента; Как бы вы изменили различные программы?

У меня есть два вопроса для этого упражнения(1) Я немного смущен тем, что "Предположим, что вместо этого мы определили максимальный подвектор как значение самого большого элемента". Означает ли это, что максимальный подвектор массива отрицательных чисел является самым большим элементом в массиве?

Например: Массив: [-1 -2 -3], максимальный подвектор: -1 Массив: [-1 2 3], максимальный подвектор: [2 3]

Извините за этот глупый вопрос, английский не мой наивный язык.

(2) Автор дал решение: "Заменить присваивание maxsofar=0 на maxsofar = -infinity". Кажется, что это решение не правильно, исходя из моего понимания вопроса.

Например: Array: [-1 -2 -3], ответ должен быть -1. Но согласно решению, это 0.

Спасибо,

Answer 1

Я с тобой согласен. Если авторское решение состоит только в том, чтобы изменить инициализацию maxsofar, тогда алгоритм не изменится вообще.