题目描述

难度分:$2600$

输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(-10^6 \leq a[i] \leq 10^6)$。

执行如下操作恰好一次：

• 把$a[i]$从$i$移动到$j$。可以原地不动，即$i=j$。

输出$a[1] \times 1 + a[2] \times 2 + … + a[n] \times n$的最大值。

输入样例$1$

4
4 3 2 5

输出样例$1$

39

输入样例$2$

5
1 1 2 7 1

输出样例$2$

49

输入样例$3$

3
1 1 2

输出样例$3$

9

算法

斜率优化DP

如果不操作，答案就是$sufsum[1]+sufsum[2]+…+sufsum[n]$，其中$sufsum[i]=\Sigma_{j=i}^{n}a[j]$，为$a$的后缀和。如果进行一次操作，那我们就需要知道某个$a[i]$插入到哪里能够得到最大的增量，有两个方向：往前或者往后插入。

假设$s$是$a$的前缀和数组，那么根据某个$a[i]$插入方向的不同，就可以分为以下两种情况：

1. 向左移动：$a[i]$移动到$j$位置，那么下标在$[j,i-1]$中的数下标就会加$1$，$a[i] \times i$会变成$a[i] \times j$。所以增量为$a[i] \times (j-i)+s[i]-s[j]=a[i] \times (j-i)-(s[j]-s[i])$。
2. 向右移动：$a[i]$移动到$j$位置，下标在$[i+1,j]$中的数下标就会减$1$，增量为$a[i] \times (j-i)-(s[j+1]-s[i+1])=a[i] \times (j-i)+a[i]-(s[j+1]-s[i+1]+a[i])=a[i] \times (j+1-i)-(s[j+1]-s[i])=a[i] \times (j’-i)-(s[j’]-s[i])$，其中$j’=j+1$。

可以发现两个式子的形式是一样的，因此目标就是要最大化增量$a[i] \times (j-i)-(s[j]-s[i])$。其中$i \in [0,n-1],j \in [0,n]$，数组下标从$0$开始。

令$p_i=(a[i],1)$，$v_j=(j,-s[j])$。则目标函数$a[i] \times (j-i)-(s[j]-s[i])=p_i \dot v_j-a[i] \times i+s[i]$。根据点积的几何意义，要求的其实就是$v_j$在$p_i$方向上的投影长度再乘以$|p_i|$，模长$|p_i|$是定值，所以要最大化投影长度。考虑$v_j$上的凸包（用$Andrew$算法计算），在凸包内的点就像是山坳，比凸包顶点的投影长度短，所以只考虑凸包顶点。

复杂度分析

时间复杂度

遍历$i \in [0,n-1]$的时候，对于每个$i$，都可能需要进行二分查找，时间复杂度为$O(log_2n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

在斜率优化的过程中，需要用一个队列存储二元组$(i,-s)$，在最差情况下需要存$O(n)$个这样的信息，所以空间复杂度为$O(n)$，这也是整个算法的额外空间复杂度。

python 代码

class vec:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def sub(self, other):
        return vec(self.x - other.x, self.y - other.y)
    def dot(self, other):
        return self.x * other.x + self.y * other.y
    def det(self, other):
        return self.x * other.y - self.y * other.x

def binary_search(n, condition):
    low, high = 0, n
    while low < high:
        mid = low + high >> 1
        if condition(mid):
            high = mid
        else:
            low = mid + 1
    return low

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    tot = mx = s = 0
    q = [vec(-1, 0)]  # 初始点
    for i in range(n):
        tot += a[i] * (i + 1)
        s += a[i]
        v = vec(i, -s)
        # 维护上凸包
        while len(q) > 1 and q[-1].sub(q[-2]).det(v.sub(q[-1])) >= 0:
            q.pop()
        q.append(v)
    s = 0
    for i in range(n):
        p = vec(a[i], 1)
        j = binary_search(len(q) - 1, lambda j: p.dot(q[j]) > p.dot(q[j + 1]))
        s += a[i]
        mx = max(mx, p.dot(q[j]) - a[i] * i + s)
    print(tot + mx)