如何编写最大子序列乘积的适当算法

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

如果所有值都为正，则可以将其替换为对数，并在日志数组中使用卡达内算法搜索最大子数组和。