Manacher算法

题目分析 本题要求在给定的数组$nums$中找到最大的回文子数组的总和。 基本思路 找回文子数组，首先要确定这个子数组的中间点，由于题目数据保证了$1 \leq nums[i] \leq 10^9$，即$nums$中所有数字都是正数，因此如果确定了一个回文子数组的中间点，为了让总和最大化， 就要让回文子数组的长度尽可能大，故问题转换成了：对于每一个位置，求出以它为中间点的回文子数组的最大长度，剩下的求和即可用前缀和直接求解。 根据这个问题，可以想到用$Manacher$算法进行求解。下面详细介绍该算法。 Manacher算法详解 正常来说，如果要用中心扩展法(即选定一个中间点，然后暴力模拟向左右两边扩展回文子数组)来检索数组中的回文子数组，不仅效率低下，同时还要根据子数组长度的奇偶性不同分两种情况考虑，比较复杂。为了解决分情况复杂的问题，$Manacher$算法提出了一个新思路：在原数组每相邻两个数字之间插入相同的分隔数字，然后只寻找长度为奇数的回文串，即可囊括原先的所有情况。 这是为什么呢？如果原数组中有一个回文串，长度是奇数，那么这个回文串中的间隔数量就是偶数，故在这个回文串中的每相邻两个数字之间都插入分隔数字后，整个数组的长度就变成了奇数；同理，如果原回文串长度是偶数，那么间隔数量就是奇数，故插入之后数组长度同样变成了奇数。综上所述，只需在新数组中寻找所有可能的奇数长度的回文串即可。这就简化了原问题。 之后就是优化计算的部分。当使用中心扩展法计算以位置$i$为中心位置的最大回文子数组长度时，如果之前在计算某一个位置的时候已经将子数组右端点扩展超过位置$i$，那么重新开始扩展的前半部分进程其实是和之前重复的，这就可以用以下方法进行简化。 定义数组$P$，其中$P[i]$表示以$i$为中点的回文子数组的最大半径。假设现在要计算$P[i]$，且已经计算出$P[:i]$中的所有值，在已知信息中，曾扩展到达的最右侧位置记为$maxRight$，其对应的子数组中点记为$maxCenter$，那么对$P[i]$的计算就可以分以下两种情况： $i> maxRight$，这时没有任何之前的信息可以利用，只能从它开始用中心扩展法计算； $i \leq maxRight$，这时$i$在以$maxCenter$为中点的最大回文子数组内，也就意味着区间$[2\times i-maxCenter, maxCenter]$在之前已经被遍历过，可以利用之前的信息： 求出$i$关于$maxCenter$的对称点$j$，即得到$j=2\times maxCenter-i$，由于两者都在回文子数组内，所以$i$周围的数字情况一定范围内和$j$周围的数字情况是相同的，因此$P[i]$的值可能是$P[j]$； 由于无法保证在位置$maxCenter$右侧的所有数据都和$2\times maxCenter-maxRight$左侧的数据相同，因此$P[i]$的值应当先和$maxRight-i+1$取一个最小值，防止错算； 从已经确定的$P[i]$最小值开始继续用中心扩展法，寻找更大的可能值。 情况2.2可以借助以下图例进行理解： ①. $i+P[j] \leq maxRight$： ②. $i+P[j]>maxRight$： 综上所述，$P[i]$可以根据情况首先确定初始值，然后再用中心扩展法继续计算，这样就可以优化掉最初循环的那一部分。 实现细节 在本题中，由于数据保证所有数字都大于等于1，且最终要求和，所以分隔数字可以采用0. 在最终计算答案时，对于每一个位置$i$求出其对应的$P[i]$后，即可得到以$i$为中点的最大回文子数组的做右端点，用前缀和进行计算并求最大值即可。 注意在循环过程中需要不断维护已知最大右端点和其对应的子数组中点位置。 复杂度 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 代码 class Solution: def getSum(self, nums: List[int]) -> int: newNums = [0] for i in nums: newNums.append(i) newNums.append(0) n = len(newNums) preSum = [0]*(n+1) for i in range(n): preSum[i+1] = preSum[i]+newNums[i] res = 0 P = [0]*n P[0] = 1 mxCenter, mxRight = 0, 0 for i in range(1, n): if i <= mxRight: j = 2*mxCenter-i P[i] = min(P[j], mxRight-i+1) l, r = i-P[i], i+P[i] while l>=0 and r<n and newNums[l] == newNums[r]: l -= 1 r += 1 P[i] += 1 res = max(res, (preSum[r]-preSum[l+1])) if r-1 > mxRight: mxRight = r-1 mxCenter = i return res