DeepSeek LeetCode 3985. 回文子数组求和 Rust实现

题目简述

3985. 回文子数组求和：给定一个整数数组 nums，找出所有回文子数组中元素和的最大值。回文子数组是指正读反读相同的连续子数组。

约束：n ≤ 10⁵，nums[i] ≥ 1。朴素 O(n²) 的中心扩展会超时，需要用 Manacher 算法 在 O(n) 时间内求出所有回文半径。

---

Rust 实现

```rust
impl Solution {
pub fn get_sum(nums: Vec<i32>) -> i64 {
let n = nums.len();
if n == 0 {
return 0;
}

// 1. 前缀和，方便 O(1) 求子数组和
let mut pref = vec![0i64; n + 1];
for i in 0..n {
pref[i + 1] = pref[i] + nums[i] as i64;
}

// 2. 构造变换数组：用 -1 作为分隔符（nums[i] >= 1）
let mut t = Vec::with_capacity(2 * n + 1);
for i in 0..n {
t.push(-1);
t.push(nums[i]);
}
t.push(-1);

// 3. Manacher 算法计算每个中心的回文半径
let m = t.len();
let mut rad = vec![0; m];
let (mut center, mut right) = (0, 0);

for i in 0..m {
let mirror = 2 * center - i;
if i < right {
rad[i] = rad[mirror].min(right - i);
}

let (mut l, mut r) = (i as isize - rad[i] as isize - 1, i + rad[i] + 1);
while l >= 0 && r < m && t[l as usize] == t[r] {
rad[i] += 1;
l -= 1;
r += 1;
}

if i + rad[i] > right {
center = i;
right = i + rad[i];
}
}

// 4. 遍历所有中心，计算回文子数组在原数组中的范围和
let mut ans = 0i64;

for i in 0..m {
let r = rad[i];
if r == 0 {
continue;
}

let mut l = i as isize - r as isize;
let mut rr = i as isize + r as isize;

// 如果边界在分隔符（偶数索引）上，向内收缩一格去掉分隔符
if l % 2 == 0 {
l += 1;
rr -= 1;
}

if l > rr {
continue;
}

// 映射回原数组索引
let orig_l = (l / 2) as usize;
let orig_r = (rr / 2) as usize;

let sum = pref[orig_r + 1] - pref[orig_l];
if sum > ans {
ans = sum;
}
}

ans
}
}
```

---

核心思路

步骤 说明
前缀和 pref[i] 表示前 i 个元素的和，子数组 [l, r] 的和 = pref[r+1] - pref[l]
变换数组 在元素间插入不会与元素冲突的分隔符（-1），使奇偶长度的回文统一处理
Manacher 线性计算每个中心的最大回文半径 rad[i]
映射回原数组 将变换数组中的回文区间映射回原数组索引，用前缀和 O(1) 求值

复杂度：时间 O(n)，空间 O(n)，可处理 n ≤ 10⁵ 的数据规模。