我最近接受了一次采访,在采访中被问到了以下算法问题。我没有能力找到O(n)的解决方案,也无法通过谷歌找到这个问题。
给定一个整数数组 A[a_0 ... a_(n-1)](包含正数和负数),生成一个数组 M[m_0 ... m_(n-1)],其中m_0 = 2,且m_i ∈ [2,...,m_(i-1)+1],使得乘积总和最大化,即要最大化a_0*m_0+a_1*m_1+...+a_(n-1)*m_(n-1)
示例:
我的O(n^2)解决方案是从m_0 = 2开始逐个增加1,只要a_i为正数。如果a_i < 0,则我们必须考虑从2到m_i-1 + 1的所有m_i,并查看哪个产生最大的乘积和。
请提出一个线性时间算法。
给定一个整数数组 A[a_0 ... a_(n-1)](包含正数和负数),生成一个数组 M[m_0 ... m_(n-1)],其中m_0 = 2,且m_i ∈ [2,...,m_(i-1)+1],使得乘积总和最大化,即要最大化a_0*m_0+a_1*m_1+...+a_(n-1)*m_(n-1)
示例:
input {1,2,3,-50,4}
output {2,3,4,2,3}
input {1,-1,8,12}
output {2,3,4,5}
我的O(n^2)解决方案是从m_0 = 2开始逐个增加1,只要a_i为正数。如果a_i < 0,则我们必须考虑从2到m_i-1 + 1的所有m_i,并查看哪个产生最大的乘积和。
请提出一个线性时间算法。