最大子段和及其变式的启示

## 2019.11.30 ## 关于最大子段和及其变式 #### $upd:$增加了一些变式的题面描述，一个$chapter$，补了一些锅 #### $chapter 1$ 最大子段和 $O(n^3)$ 枚举区间起点和终点，暴力求和； $O(n^2)$ 枚举左右端点时 $j=i$ -> $m$ 可以动态维护$i$~$j$的前缀和； $O(n^2)$ 预处理前缀和，枚举左右端点时$O(1)$计算； $O(nlogn)$ 枚举中点,分别往前面和后面计算一个包含$center$的最大子段和，预处理前缀和一次判断是$O(1)$的； $O(n)$ 考虑$dp$，设状态$f[i]$为包含且以$a[i]$结尾的最大值，方程：$f[i] = max(~f[i-1]~,~0~) + a[i]$； $O(n)$ 一个以$a[i]$结尾最大子段的定义：$sum[i]-min(sum[k])~(1<=k<i)$ ，计算$min(~sum[k]~)$可以动态维护一个前缀和的最小值； #### $chapter 2$ 子段长度不大于m的最大子段和 $O(n)$ 仍然考虑最大子段和的定义，动态维护$min(sum[k])~(i-m<=k<i)$，使用单调队列维护，队列中的数递增(参考$P1886$滑动窗口)； #### $chapter 3$ 子段长度不小于m的最大子段和 $O(nlongn)$ 可以将分治思想中的枚举中点改成枚举一个中段，同理；(但是显然需要枚举一个段的话编码难度会提升) $O(n)$ 先计算一次不限长最大子段和，再从头开始，枚举每一个长为m的子段，在它前面拼上以$a[i-1]$结尾的最大子段和；方程：$f'[i] = max(~f[i-1]~,~0~) + sum[i+m] - sum[i-1]$，最后取一个$max$； $O(n)$ 动态维护$min(sum[k])~(1<=k<=i-m)$，比上一种编码简洁，只需要一次循环，维护前缀和； #### $chapter 4$ 环状最大子段和 在最大子段和的基础上，认为a[1]和a[n]是相邻的。 $O(n)$ 将序列倍长，就可以做一遍长度不大于m的最大子段和 $O(n)$ 考虑子段是否过端点，过端点就取反，其实就是求一个最小子段和；不过端点就没有影响。 #### $chapter 5$ 环状最大两段子段和 $O(n^2)$ 考虑破环成链，枚举破坏的断点$O(n)$，在链上求最大两段子段和；维护一个$f1[i]$为以$a[i]$结尾的最大子段和，一个$f2[i]$为以$a[i]$开头的最大子段和；(其实就是倒着求一遍)复杂度$O(3n)$； $O(n)$ 对于答案可能有的所有情况，一种是有一段跨过了端点，另一种是没有跨过端点；所以可以先求一遍两段最大子段和，再对整个序列取反，再求一遍(这时其实就是求出两段的最小子段和，用总和减去后就是跨过端点的两段最大子段和)，这时把两种情况取一个$max$； #### $chapter 6$ 最大m段子段和 给定由n个整数（可能为负整数）组成的序列， 以及一个正整数m，要求确定序列m个不相交子段， 使得这m个子段的总和达到最大，求出最大和。 $O(n^{2m})$ 不用说了，暴力枚举每一段的左右端点，求和； $O(n^m)$ 还可以再优化，动态维护每一段当前$a[i]$之前，上一段结尾之后的前缀和$min$，可以递归实现；当然递归的形式会减慢速度； $O(n^3m)$ 难道不像一个区间dp？？我们设状态$f1[i][j][k]$为区间$[i,j]$内已经分配了k段的最大值；方程为：$f1[i][j][k]=max(f1[i][j][k],f1[i][p][k-1]+f1[p+2][j][1])~(p>i,p+2<=j)$；这转移显然有： for(int p=1;p<=m;p++) for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) for(int q=i+1;q+2<=j;q++) f[i][j][p]=max(f[i][j][p],f[i][q][p-1]+f[q+2][j][1]); $O(n^2m)$ 其实本来方程中枚举段数也需要一层循环，但是我们发现这是一个分段问题，和选取的段数先后无关，故我们可以直接把一段拼上$p-1$段。(对于这种dp我更愿意称它为分段dp而不是区间dp)接着我们将方程转化一下，会发现$f1[q+2][j][1]$其实就是$sum[j]-sum[q+1]$！这时方程变为$f1[i][j][k]=max(f1[i][j][k],f1[i][p][k-1]+sum[j]-sum[q+1])~(p>i,p+2<=j)$；我们再次观察，发现转移可以优化：第一维所涉及的转移全部是$i$！这时把第一维去掉，状态定义转化为区间$[1,j]$内已经分配了k段的最大值：$f[j][k]$；这时转移就有： for(int p=1;p<=m;p++) for(int j=1;j<=n;j++) for(int q=i+1;q+2<=j;q++) f[j][p]=max(f[j][p],f[j][p-1]+sum[j]-sum[q+1]); $O(nm)$ 上一种方法的方程已经变为$f1[j][p]=max(f1[j][p],f[j][q][p-1]+sum[j]-sum[q+1])$，我们再看看还是否可以优化。我们发现，求m段子段的过程中，当我已经求出前$i$个元素，$k$段的时候，我要做的，其实就是考虑向后多少个元素后再重新开一段。所以该状态为$f[i][j][0/1]$表示前$i$个元素，$j$段，第i个元素是否选的最大子段和。转移就好写了： f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0])+a[i]; f[i][j][0]=max(f[i-1][j][1],f[i-1][j][0]); #### $chapter 7$ 只含正整数的不小于$S$($S<=10^9$)的最小子段和的长度($n<=100000$) 给出了N个正整数（10 <N <100 000）的序列， 每个正整数均小于或等于10000，并给出了一个正整数S（S <100 000 000）。 编写程序以查找序列中连续元素的子序列的最小长度，其总和大于或等于S。 $O(n^2)$ 枚举左右端点，用前缀和计算$O(1)$，取最小值； $O(n)$ 考虑二分答案，每次计算不超过当前长度下的最大子段和能否不小于$S$，具体操作见$chapter2$ $O(n)$ 一种新的方法：尺取法。因为题目所给数均为正整数，所以可以设一个队首和一个队尾，总和小于$S$就往后加一个数，大于$S$就在最前面减一个数。(决策的单调性是应用尺取法的前提，老师将它比作虫子向前蠕动的样子)同样，尺取法不仅能求长度，也能求大于$S$的最小子段和。而二分得到的答案，最短的不一定是最接近$S$的。 #### $chapter 8$ 含负数的不小于$S$($S<=10^9$)的最小子段和的长度($n<=100000$) $O(nlogn)$ 现将所有前缀和算出来，离散化；题目所求即为求一个$min(j-i)$，满足$sum[j]-sum[i]>=S~(1<=i<=j,sum[i]=min(sum[1]~to~sum[j-1]))$；即$sum[j]-S>=sum[i]$。开一个值域树状数组，$c[i]$表示的是前缀和为$i$(离散化后的)的前缀的最后一个位置。相当于在树状数组内每次查询小于$sum[j]-S$的那一段中位置的最大值。这样就求出了最小长度；而对于最小值的话，查询第一个$c[i]!=-1$就可以了。 #### $chapter 9$ 含/不含负数的不大于S的最大子段和的长度/值 $O(???)$ 这些其实都可以类比上一个$chapter$的做法，不说了。 #### $chapter 10$ 一些其他的 有些题目中要求的是不相邻的两个子段，有些又没有要求。其实不相邻意味着两个子段之间至少隔一个数；不然的话，两个子段虽然接在了一起，但是仍可以认为是两个子段。这个时候其实关于转移，只需要转移$a[i]~to~a[j]$改成$a[i+1]~to~a[j+1]$就可以了。 ### 启示：其实我们在优化算法时，优化枚举的核心即为减少枚举过程中的重复计算。