2026-10-10：回文子数组求和。用go语言，现有一个整数序列。请从其中选出若干个位置相邻且数量不为零的连续元素，要求这段元素按原顺序读和按相反顺序读完全一致，也就是具有回文性质。对于所有满足这种条件的连续片段，计算其中所有整数相加的结果，并找出可能得到的最大值。最后返回这个最大和。
1 <= nums.length <= 100000。
1 <= nums[i] <= 1000000000。
输入： nums = [10,10]。
输出： 20。
解释：
整个数组 [10,10] 是回文子数组。因此，最大元素和为 10 + 10 = 20。
题目来自力扣3985。
大体步骤如下：
第一步，把原数组改造成一个扩展数组。
原数组中的元素都是正整数，代码在每两个原元素之间以及两端插入一个特殊分隔值 -1，使得原来长度为奇数和偶数的回文片段，在扩展数组里都变成以某个位置为中心的奇回文。扩展数组开头放一个 -2，结尾放 -1 和 -3 作为哨兵，用来避免边界判断，并保证向两边扩展时一定会停止。这样原数组下标和扩展数组下标之间形成固定对应关系，原数组的连续片段可以映射到扩展数组中的回文区间。
第二步，计算扩展数组中每个中心的最长回文半径。
代码维护一个 halfLen 数组，其中 halfLen[i] 表示以扩展数组第 i 个位置为中心时，最长的回文半径。这个半径决定了扩展数组中回文覆盖的闭区间是左端 i - halfLen[i] + 1，右端 i + halfLen[i] - 1。
为了加速计算，使用 Manacher 算法的思想：维护当前已经找到的、右边界最靠右的回文中心 boxM，以及它的右边界再右移一位的位置 boxR。遍历每个可能的中心 i 时，如果 i 还在 boxR 的左边，就利用它关于 boxM 的对称点 i' 来初步确定回文半径。具体是取对称点的回文半径和 boxR - i 中较小的那个作为初始半径。然后从这个初始半径继续向两边暴力比较，只要两边字符相同，半径就加一，并更新 boxM 和 boxR。因为 boxR 只会不断向右移动，所以虽然内部有暴力扩展，但总扩展次数是线性的。
第三步，预处理原数组的前缀和。
代码建立一个前缀和数组 sum，其中 sum[0] 为 0，sum[k+1] 表示原数组前 k+1 个元素的和。这样任意原数组闭区间 [L, R] 的元素和都可以用 sum[R+1] - sum[L] 在常数时间内算出。由于元素值可能很大，累加结果需要用 64 位整数保存。
第四步，枚举所有回文中心，求对应原数组回文片段的和，并取最大值。
对于扩展数组中的每个中心 i，取出它的最长回文半径 hl。根据扩展数组和原数组的下标转换关系，这个回文片段对应到原数组中的闭区间是：左端为 (i - hl) / 2，右端为 (i + hl) / 2 - 2。
于是该区间的元素和就是 sum[(i + hl) / 2 - 1] - sum[(i - hl) / 2]。代码用这个和不断更新答案，最终保留最大值。
因为题目保证原数组元素都是正数，所以对于同一个中心来说，最长的回文片段一定包含所有更短的回文片段，且元素和更大，因此只需要检查每个中心的最长回文即可。
举例来说，输入 nums = [10, 10]。扩展数组构造后，能够找到一个覆盖两个 10 的回文片段，它对应原数组区间 [0, 1]，元素和为 10 + 10 = 20，所以最终输出 20。
总的时间复杂度：
构造扩展数组、Manacher 计算回文半径、建立前缀和、枚举所有中心，这些步骤都是线性的。因此总时间复杂度是 O(n)，其中 n 是原数组 nums 的长度。
总的额外空间复杂度：
扩展数组、回文半径数组 halfLen、前缀和数组 sum 的长度都与 n 成正比，因此总额外空间复杂度是 O(n)。
Go完整代码如下：
package main
import (
"fmt"
)
func getSum(s []int) (ans int64) {
// 将 s 改造为 t，这样就不需要分 len(s) 的奇偶来讨论了，因为新数组 t 的每个回文子数组都是奇回文子数组（都有回文中心）
// s 和 t 的下标转换关系：
// (si+1)*2 = ti
// ti/2-1 = si
// ti 为偶数（2,4,6,...）对应 s 中的奇回文子数组
// ti 为奇数（3,5,7,...）对应 s 中的偶回文子数组
t := append(make([]int, 0, len(s)*2+3), -2)
for _, c := range s {
t = append(t, -1, c)
}
t = append(t, -1, -3)
// 定义一个奇回文子数组的回文半径=(长度+1)/2，即保留回文中心，去掉一侧后的剩余子数组的长度
// halfLen[i] 表示在 t 上的以 t[i] 为回文中心的最长回文子数组的回文半径
// 具体地，闭区间 [i-halfLen[i]+1, i+halfLen[i]-1] 是 t 上的一个回文子数组
// 由于 t 中回文子数组的首尾元素一定是 -1，根据下标转换关系，
// 可以得到其在 s 中对应的回文子数组的区间为 [(i-halfLen[i])/2, (i+halfLen[i])/2-2]，用这个结论去计算子数组和
halfLen := make([]int, len(t)-2)
halfLen[1] = 1
// boxR 表示当前右边界下标最大的回文子数组的右边界下标+1（初始化成任意 <= 0 的数都可以）
// boxM 为该最大回文子数组的中心位置，二者的关系为 boxR = boxM + halfLen[boxM]
boxM, boxR := 0, 0
for i := 2; i < len(halfLen); i++ { // 循环的起止位置对应着原数组的首尾元素
hl := 1
if i < boxR {
// 记 i 关于 boxM 的对称位置 i'=boxM*2-i
// 若以 i' 为中心的最长回文子数组范围超出了以 boxM 为中心的回文子数组的范围（即 i+halfLen[i'] >= boxR）
// 则 halfLen[i] 应先初始化为已知的回文半径 boxR-i，然后再继续暴力匹配
// 否则 halfLen[i] 与 halfLen[i'] 相等
hl = min(halfLen[boxM*2-i], boxR-i)
}
// 暴力扩展
// 算法的复杂度取决于这部分执行的次数
// 由于扩展之后 boxR 必然会更新（右移），且扩展的的次数就是 boxR 右移的次数
// 因此算法的复杂度 = O(len(t)) = O(len(s))
for t[i-hl] == t[i+hl] {
hl++
boxM, boxR = i, i+hl
}
halfLen[i] = hl
}
sum := make([]int64, len(s)+1)
for i, x := range s {
sum[i+1] = sum[i] + int64(x)
}
for i := 2; i < len(halfLen); i++ {
hl := halfLen[i]
// 见上面注释
ans = max(ans, sum[(i+hl)/2-1]-sum[(i-hl)/2])
}
return
}func main() {
nums := []int{10, 10}
result := getSum(nums)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
def get_sum(nums: List[int]) -> int:
n = len(nums)
# 构造扩展数组 t
t = [-2]
for x in nums:
t.extend([-1, x])
t.extend([-1, -3])
# half_len[i] 表示以 t[i] 为中心的最长回文半径
half_len = [0] * (len(t) - 2)
half_len[1] = 1
box_m, box_r = 0, 0
for i in range(2, len(half_len)):
hl = 1
if i < box_r:
hl = min(half_len[box_m * 2 - i], box_r - i)
while t[i - hl] == t[i + hl]:
hl += 1
box_m, box_r = i, i + hl
half_len[i] = hl
# 前缀和
prefix = [0] * (n + 1)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
ans = 0
for i in range(2, len(half_len)):
hl = half_len[i]
ans = max(ans, prefix[(i + hl) // 2 - 1] - prefix[(i - hl) // 2])
return ansif __name__ == "__main__":
nums = [10, 10]
result = get_sum(nums)
print(result)
C++完整代码如下：
long long getSum(const std::vector& s) {
// 将 s 改造为 t，这样就不需要分 len(s) 的奇偶来讨论了，
// 因为新数组 t 的每个回文子数组都是奇回文子数组（都有回文中心）
// s 和 t 的下标转换关系：
// (si + 1) * 2 = ti
// ti / 2 - 1 = si
// ti 为偶数（2,4,6,...）对应 s 中的奇回文子数组
// ti 为奇数（3,5,7,...）对应 s 中的偶回文子数组
std::vector t;
t.reserve(s.size() * 2 + 3);
t.push_back(-2);
for (int c : s) {
t.push_back(-1);
t.push_back(c);
}
t.push_back(-1);
t.push_back(-3);
// halfLen[i] 表示在 t 上的以 t[i] 为回文中心的最长回文子数组的回文半径
// 闭区间 [i - halfLen[i] + 1, i + halfLen[i] - 1] 是 t 上的一个回文子数组
// 由于 t 中回文子数组的首尾元素一定是 -1，根据下标转换关系，
// 可以得到其在 s 中对应的回文子数组区间为：
// [(i - halfLen[i]) / 2, (i + halfLen[i]) / 2 - 2]
std::vector halfLen(t.size() - 2);
halfLen[1] = 1;
// boxR 表示当前右边界下标最大的回文子数组的右边界下标 + 1
// boxM 为该最大回文子数组的中心位置，关系为 boxR = boxM + halfLen[boxM]
int boxM = 0, boxR = 0;
for (int i = 2; i < (int)halfLen.size(); ++i) {
int hl = 1;
if (i < boxR) {
// 记 i 关于 boxM 的对称位置 i' = boxM * 2 - i
// 若以 i' 为中心的最长回文子数组范围超出了以 boxM 为中心的回文子数组范围，
// 则 halfLen[i] 先初始化为已知的回文半径 boxR - i，然后再继续暴力匹配；
// 否则 halfLen[i] 与 halfLen[i'] 相等
hl = std::min(halfLen[boxM * 2 - i], boxR - i);
}
// 暴力扩展
while (t[i - hl] == t[i + hl]) {
++hl;
boxM = i;
boxR = i + hl;
}
halfLen[i] = hl;
}
// 前缀和
std::vector sum(s.size() + 1, 0);
for (int i = 0; i < (int)s.size(); ++i) {
sum[i + 1] = sum[i] + s[i];
}
long long ans = 0;
for (int i = 2; i < (int)halfLen.size(); ++i) {
int hl = halfLen[i];
ans = std::max(ans, sum[(i + hl) / 2 - 1] - sum[(i - hl) / 2]);
}
return ans;
}int main() {
std::vector nums = {10, 10};
long long result = getSum(nums);
std::cout << result << std::endl;
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴