2026-10-10：回文子数组求和。用go语言，现有一个整数序列。请从其中选出若干个位置相邻且数量不为零的连续元素，要求这段元素按原顺序读

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 ans

if __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助力您的未来发展。