出题人题解 | #小A与最大子段和#

原题解链接：https://ac.nowcoder.com/discuss/154293

令$A_x={\sum }_{i=1}^x{a}_i\times i,B_x={\sum }_{i=1}^x{a}_{i}A\_\{x\}=\backslash sum\_\{i=1\}^\{x\}\; a\_\{i\}\; \backslash times\; i,\; B\_\{x\}=\backslash sum\_\{i=1\}^\{x\}\; a\_\{i\}$

$f_{i}f\_i$ ​ 表示以$ii$为右端点的 “最大子段和”，假设左端点为$j+1j+1$

则

$f_i={\sum }_{k=j+1}^i{a}_k\times (k-j)f\_\{i\}=\backslash sum\_\{k=j+1\}^\{i\}\; a\_\{k\}\; \backslash times(k-j)$

$=A_i-A_j-(B_i-B_j)\times j=A\_\{i\}-A\_\{j\}-\backslash left(B\_\{i\}-B\_\{j\}\backslash right)\; \backslash times\; j$

$=A_i-j\times B_i-A_j+j\times B_j=A\_\{i\}-j\; \backslash times\; B\_\{i\}-A\_\{j\}+j\; \backslash times\; B\_\{j\}$

$y=j\times B_j-A_j,x=j,k=B_i,b=f_i-A_{i}y=j\; \backslash times\; B\_\{j\}-A\_\{j\},\; x=j,\; k=B\_\{i\},\; b=f\_\{i\}-A\_\{i\}$

可得$y=kx+by=kx+b$，可以使用斜率优化

希望最大化截距，且横坐标$xx$单调，斜率$kk$不单调，所以用单调栈维护凸壳，在凸壳上三分$DPDP$值/二分斜率

另有一种$kk$单调，$xx$不单调的推法（鸣谢验题人）

$f_{i}f\_i$ ​ 表示以 $ii$ 为左端点的"最大子段和"

令 $s_i={\sum }_{j=i}^n{a}_j,c_i={\sum }_{j=i}^n{s}_{j}s\_i=\backslash sum\_\{j=i\}^na\_j,\; c\_i=\backslash sum\_\{j=i\}^ns\_j$

$f_i={\sum }_{j=i}^{k-1}{s}_j-s_k=c_i-c_k-s_k\times (k-i)f\_\{i\}=\backslash sum\_\{j=i\}^\{k-1\}\; s\_\{j\}-s\_\{k\}=c\_\{i\}-c\_\{k\}-s\_\{k\}\; \backslash times(k-i)$

$c_j+s_j\times j=i\times s_j+c_i-f_{i}c\_\{j\}+s\_\{j\}\; \backslash times\; j=i\; \backslash times\; s\_\{j\}+c\_\{i\}-f\_\{i\}$

$y=c_j+s_j\times j,k=i,x=s_j,b=c_i-f_{i}y=c\_\{j\}+s\_\{j\}\; \backslash times\; j,\; k=i,\; x=s\_\{j\},\; b=c\_\{i\}-f\_\{i\}$

(上面的$kk$变成$jj$了)

这里要最小化截距，使用$cdqcdq$分治

复杂度$O(nlogn)O(nlogn)$ ，时限比较宽松，两个$loglog$也可以通过

几个关于这个写法代码细节的提示：

• 排序时只用横坐标当关键字（横坐标相同的情况）
• 维护凸壳时$\le \backslash leq$或者$\ge \backslash geq$ 写成或者$>>$
• $dpdp$数组初值是$00$（题目中要求非空子段）

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 5;
ll a[N], c[N], dp[N];
int n, q[N], l, r, t[N];
ll f(int x) {
  return x * a[x] + c[x];
}
ll g(int x) {
  return a[x];
}
bool cmp(int x, int y) {
  return g(x) < g(y) || (g(x) == g(y) && f(x) > f(y));
}
void solve(int L, int R) {
  if (L == R) {
    dp[L] = a[L] - a[L + 1];
    return;
  }
  int mid = (L + R) >> 1;
  solve(L, mid); solve(mid + 1, R);
  l = r = 0;
  sort(t + mid + 1, t + R + 1, cmp);
  for (int i = mid + 1; i <= R; i++) {
    while (l + 1 < r) {
      if (g(t[i]) == g(q[r - 1]) || (f(t[i]) - f(q[r - 1])) * (g(q[r - 1]) - g(q[r - 2])) <= (f(q[r - 1]) - f(q[r - 2])) * (g(t[i]) - g(q[r - 1]))) --r;
      else break;
    }
    q[r++] = t[i];
  }
  sort(t + L, t + mid + 1);
  for (int i = L; i <= mid; i++) {
    int p = t[i];
    while (l + 1 < r && f(q[l + 1]) - f(q[l]) <= p * (g(q[l + 1]) - g(q[l]))) l++;
    dp[p] = max(dp[p], c[p] - c[q[l]] - (q[l] - p) * a[q[l]]);
  }
}
int main() {
  cin >> n; t[n + 1] = n + 1;
  assert(n > 0 && n <= 200000);
  for (int i = 1; i <= n; i++) cin >> a[i], t[i] = i, assert(a[i] >= -2000 && a[i] <= 2000);
  for (int i = n; i; i--) a[i] += a[i + 1];
  for (int i = n; i; i--) c[i] = a[i] + c[i + 1];
  solve(1, n + 1);
  cout << *max_element(dp + 1, dp + 1 + n);
  return 0;
}