区间最值问题已知一个n个数序列a[i],在序列a中区间[l,r]之间找出最小值a[p],求出a[p]*(a[l]+a[l+1]+...+a[r])的最大值

Question

区间最值问题
已知一个n个数序列a[i],在序列a中区间[l,r]之间找出最小值a[p],求出a[p]*(a[l]+a[l+1]+...+a[r])的最大值

Answer 1

你是要一个算法吧?
我想了半天,只有一个 O(n^2) 的算法,而且要假设 a[i] 都是正数（如果有正有负就太麻烦了）.
这个可以叫动态规划算法,也可以什么都不叫,因为它就是个最简单的动态规划.
总的思路：
r 从 1 到 n,对每个 r,在前 r 个数：a[1],a[2],...,a[r] 中,求：
在所有以 r 结尾的区间 [k,r]（其中 k = 1,2,...,r）中,f(k,r) = a[p]*(a[k]+a[k+1]+...+a[r]) 中最大的那个.
这样,总的最大值（即题目所求）就是所有 r 从 1 到 n 中最大的那个.
首先我们造一个辅助序列：S[r] = a[1]+a[2]+...+a[r]
这样对任意的 k,我们就能在 O(1) 时间算出：a[k]+a[k+1]+...+a[r] = S[r] - S[k-1]
然后,对每个 r,定义一个 M 序列：
如果 a[k] 是 a[k],a[k+1],...,a[r] 中的最小值,那么就把 k 放进 M 序列中.
k 也是从右往左依次放入 M 序列,所以 M[1] < M[2] < ...< M[T(r)] = r,其中 T(r) 是 M 序列的长度.
对于 M 中的一个数：M[i],所有以 M[i] 为最小值的序列中,f 值最大的一个是从 M[i-1]+1 到 r 的序列：
a[M[i]] * (a[M[i-1]+1] + a[M[i-1]+2] + ...+ a[r]) = a[M[i]] * (S[r] - S[M[i-1]])
所以,我们只要对每个 M 中的值,都算出：a[M[i]] * (S[r] - S[M[i-1]]),取最大的一个就行了.
当我们从 r 到 r+1 时,需要更新 M 序列.
只需将 a[r+1] 分别与 a[M[T(r)]],a[M[T(r)-1]],...相比,如果 a[r+1] 小,就把旧的 M 序列中的数删掉,最后在 M 序列的末尾添上 r+1 即可.
时间复杂度：
对每个 r,其 M 序列最多有 O(n) 个数,每个 a[M[i]] * (S[r] - S[M[i-1]]) 都可以在 O(1) 时间算出,所以最后是 O(n^2)
关于更多的思考.
能否优化：能,但并不改变 O(n^2) 的时间复杂度.
假设第 r 步时,M[i] 是 f 值最大的那个.
那么在后面的 r+1,r+2,...步时,只要 M[i] 还在 M 序列中,那么 M[i] 的 f 值永远比 M[1],M[2],...,M[i-1] 的 f 值大.
但 M[i] 可能从 M 序列中删掉,这样的话,M[1],M[2],...,M[i-1] 就又可能成为最大的 f 值了.
所以优化是这样：给 M 序列造一个辅助序列 flag,如果 M[i] 曾经取到最大 f 值,那么 flag[i] = 1,否则 flag[i] = 0.
这样我们不需要对所有的 M[i] 计算 f 值,只要（在 M 序列中）从右到左依次计算 M 值,直到碰到第 1 个 flag[i] = 1 的即可.
就说这么多了,如果对哪个细节不清楚,就追问一下吧.