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

题目简述3985. 回文子数组求和给定一个整数数组 nums找出所有回文子数组中元素和的最大值。回文子数组是指正读反读相同的连续子数组。约束n ≤ 10⁵nums[i] ≥ 1。朴素 O(n²) 的中心扩展会超时需要用 Manacher 算法 在 O(n) 时间内求出所有回文半径。---Rust 实现rustimpl Solution {pub fn get_sum(nums: Veci32) - 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] 1let 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[r1] - pref[l]变换数组 在元素间插入不会与元素冲突的分隔符-1使奇偶长度的回文统一处理Manacher 线性计算每个中心的最大回文半径 rad[i]映射回原数组 将变换数组中的回文区间映射回原数组索引用前缀和 O(1) 求值复杂度时间 O(n)空间 O(n)可处理 n ≤ 10⁵ 的数据规模。