algorithm - 如何编写最大子序列乘积的正确算法

给定数组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

    }

最佳答案

如果所有值都为正值，则可以将它们替换为对数，并在日志数组中使用Kadane’s Algorithm搜索max sub array sum。

关于algorithm - 如何编写最大子序列乘积的正确算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54848163/