最大子段和系列问题学习笔记

(\)

最大子段和 (Theta(N))

给出一个数列，选出其中连续且非空的一段，使得这一子段和最大。
(f[i])表示以(i)结尾的最大子段和，转移为(f[i]=num[i]+max(f[i-1],0))，可滚动数组优化。
```
for(int i=1;i<=n;++i) ans=max(ans,(now=num[i]+max(now,0));
```

(\)

限定最长长度最大子段和 (Theta(N))

给出一个数列，选出其中连续非空且长度不超过(M)的一段，使得这一子段和最大。
考虑前缀和优化，一个子段和可以转化成两个前缀和相减，但枚举端点复杂度太高，不妨只枚举右端点，维护一个单调队列存储左端点，即可( ext{O}(1))地得到最优转移点。注意答案初始化是第一个元素的值而非(0)；

注意向后移动时队头可能会不合法，需及时清理；队尾压入元素时，尾部出队至队尾优于当前元素为止。

hd=tl=1; q[1]=1; ans=sum[1];
for(R int i=2;i<=n;++i){
	while(tl>=hd&&sum[i]<=sum[q[tl]]) --tl;
	while(tl>=hd&&i-q[hd]>m) ++hd; q[++tl]=i;
	ans=max(ans,sum[i]-sum[q[hd]]);
}

(\)

带修改限定区间最大子段和单次(Theta(N log(N)))

给出一个数列，多次询问给定区间([L,R])内最大子段和。
线段树维护每一个区间前缀最大，后缀最大，区间和，区间最大，分治的思想分情况讨论处理。

(\)

K段最大子段和 (Theta (NK)/ ext{O}((N+K)log(N)))

给出一个序列，选出其中连续且非空的(K)段，使得这(K)段和最大。

法一：(DP) (Theta (NK))

(f[i][j][0/1])表示前(i)个数分成(j)段，当前数字选/没选在最后一段里的最优答案。
(0)部分的转移：继承上一段，从上一位置同一个段数的两个状态转移。
```
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
```
(1)部分的转移：继承上一段，从上一位置同一段数(1)状态转移(/)新开一段，从上一状态上一段数两个状态转移：
```
f[i][j][1]=num[i]+max(f[i-1][j][1],max(f[i-1][j-1][1],f[i-1][j-1][0]));
```
可滚动数组，若题目为至多(K)段则答案为所有段数取(max)，固定(K)段则直接取(max(f[n][k][0],f[n][k][1]))；

法二：贪心+堆 ( ext O ((N+K)log(N)))

注意到选取有一些隐藏的规则：
- 所有连续正数段若选入答案，必定一起选
- 如果两个正数段合并，必然跨过其间所有负数，所以每个连续负数若选择，必定一起选
- 头和尾的负数一定不被选入答案
按照上面的规则即可缩点，并去掉头尾无用的数字，得到一个两端均为正数，相邻两项负号不同的数列。

注意实现过程中只能把(0)归给一侧，否则可能会将一些负数段和正数段合并。

for(R int i=1;i<=n;++i) a[i]=rd();
while(a[n]<=0&&n) --n;
while(a[s]<=0&&s<n) ++s;
for(;s<=n;++s) 
  ((a[s]<=0&&a[s-1]<=0)||(a[s]>0&&a[s-1]>0))?num[tot]+=a[s]:num[++tot]=a[s];

考虑先将所有正数和以及正数段个数(cnt)统计出来，若(cnt>K)，再从中去掉或减掉一些部分得到答案。
将所有数段取绝对值放到小根堆里，每次取堆顶让答案减掉，一共进行(cnt-K)次。
正确定可以分类讨论得到：
- 若原数段是正数段，则代表不选这个正数段，小根堆满足贪心策略
- 若原数段是负数段，则代表合并其两侧的正数段要付出的代价，同样满足贪心策略
注意，若合并到左右端点时，必定是取了两个端点的整数，其内侧的第一个负数段必定不能再选入答案，所以直接将端点向内收回两个位置。

注意到如果选掉了一个负数，其两侧的正数再选掉会导致选掉这个负数没有意义，正数同理，所以可以拿 ([ CTSC 2007 ] Backup) 的方法合并每次选掉的段。

while(m--){
    while(q.top().first!=-num[q.top().second]) q.pop();
    int now=q.top().second; q.pop();
    int pr=pre[now],nx=nxt[now];
    ans-=num[now];
    if(!pr){num[nx]=inf;pre[nxt[nx]]=0;}
    else if(!nx){num[pr]=inf;nxt[pre[pr]]=0;}
    else{
      num[now]=num[pr]+num[nx]-num[now];
      q.push(make_pair(-num[now],now));
      num[pr]=num[nx]=inf;
      nxt[pre[now]=pre[pr]]=pre[nxt[now]=nxt[nx]]=now;
    }
}

(\)

环状(K段)最大子段和 (Theta (NK)/ ext{O}((N+K)log(N)))

给出一个环状数组((N-1)的下一个是(1))，选出其中连续且非空的(K)段，使得这(K)段和最大。
不考虑环状时思路同上，考虑环状，无需枚举端点破环成链，考虑在(1)处断开，答案只有可能穿过(1)和(N-1)或不穿过两种，所以进行两次链状(K)段最大子段和即可，一次处理从(1)处断开的链对应的(K)段最大子段和，另一次处理从(1)处断开必须包含(1)和(N-1)的(K+1)段最大子段和。
复杂度对应上述两种，对于第二次处理法一很好改，法二从头一直向后加成正数，尾一直向前加成正数。

(\)

最大子树和 (Theta(N))

给出一棵无根树，每个节点有点权，求删掉任意数目任意长度的链并保证剩下的图联通的情况下，使得剩下的图点权和最大值。
将最大子段和移到树上，问题的本质并没有变化。树上(DP)即可，因为如何旋转都不影响答案，不妨设(1)号节点为根，设(f_i)表示必须选(i)号节点，其子节点构成的子树任意选择的答案。
对于每棵子树的答案是否选取思路与最大子段和相同，注意在每个节点都要更新答案。

inline void dfs(int u,int fa){
  f[u]=val[u];
  for(R int i=hd[u],v;i;i=e[i].nxt)
  if((v=e[i].to)!=fa){
    if(!f[v]) dfs(v,u);
    f[u]+=max(0,f[v]);
  }
  ans=max(ans,f[u]);
}
dfs(1,-1); printf("%d
",ans);

(\)

最大有权子正方形 (Theta (NM))

给出一个(01)矩阵，求最大的内部全部有权的子正方形边长和个数。
(f[i][j])表示以((i,j))为右下角，最大合法子正方形的边长，若当前位置有权，当前答案为左，上，左上三个点的答案取(min)+ 1，代表左下，左上，右上三个顶点最长边长加上当前点扩张出的边长，方案数再扫一遍即可。
```
for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
        if(val[i][j]) ans=max(ans,f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1);
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(f[i][j]==ans) ++cnt;
```

(\)

最大有权子矩形(Theta(NM))

给出一个(01)矩阵，求最大的内部全部有权的子矩形面积。
(Theta(NM))预处理出每个点最长可向下延申长度。

对每一行处理，视对应长度为该位置子矩形高，单调栈求解，弹栈时更新答案即可。

stack[1].height=pos[x][1]; stack[1].length=1;
for(int i=2;i<=m;++i){
    temp=0;
    while(stack[top].height>=pos[x][i]&&top>0){
        temp+=stack[top].length;
        maxs=max(maxs,stack[top--].height*temp);
    }
    stack[++top].height=pos[x][i]; stack[top].length=temp+1;
}
temp=0;
while(top>0){
    temp+=stack[top].length;
    maxs=max(maxs,stack[top--].height*temp);
}
ans=max(ans,maxs);

(\)

最大权值和子矩阵 (Theta (N^3))

给出一个有权矩阵，求权值和最大的子矩阵的权值和。
枚举左上角和右下角复杂度太高，考虑只枚举行的限制，假设限制答案矩阵上边界为第(i)行，下边界为第(j)行，那么问题转化为左右边界的选取。将所有相同的列坐标位置数字加在一起，就转化为了最大子段和问题。

预处理出来每一列对应的前缀和，枚举上下边界后做一遍对应各列区间和的最大子段和即可。

for(R int i=1;i<=n;++i)
		for(R int j=1;j<=n;++j) sum[i][j]=sum[i-1][j]+rd();
for(R int i=0;i<n;++i)
	for(R int j=i+1;j<=n;++j)
		for(R int k=1,temp=0;k<=n;++k) ans=max(ans,(temp=sum[j][k]-sum[i][k]+max(temp,0)));

(\)