Как написать правильный алгоритм для максимального продукта подпоследовательности

Question

Задан массив A, пытающийся решить максимальный алгоритм задачи задачи с подпоследовательностью.Таким образом, функция должна возвращать начальный и конечный индексы подпоследовательности , которая имеет наибольшее произведение с использованием динамического программирования .Например:

funcSubSeqMaxProduct(A[1..n]) {

return j,k  #Where j<=k and A[j,...k]  is the maximum sub sequence product.

}

То, что я пробовал до сих пор:

funcSubSeqMaxProduct(A[1..n]) {
   for i = 1 to n
     pro(i) = max(ai, pro(i-1)*ai)
     j = max(pro(i))

    #something I am struggling how to get the correct indices of lower and upper bound.
    return j,k 

    }

Answer 1

Если все ваши значения положительны, вы можете заменить их на их логарифмы, а в поиске по массиву журналов найти максимальную сумму подмассива с помощью Алгоритма Кадане .