在数学和数据处理中，寻找序列中连续子序列的最大乘积是一个经典问题。在 Exercism 的 “largest-series-product” 练习中，我们需要实现一个函数来计算数字字符串中指定长度连续子序列的最大乘积。这不仅能帮助我们掌握滑动窗口算法和数值计算技巧，还能深入学习Rust中的错误处理、迭代器使用和性能优化。

什么是Largest Series Product？

Largest Series Product（最大序列乘积）问题要求我们在一个数字字符串中找到指定长度的连续子序列，使得这些数字的乘积最大。例如：

在字符串"123456789"中查找长度为3的子序列的最大乘积：

  • “123” → 1×2×3 = 6
  • “234” → 2×3×4 = 24
  • “345” → 3×4×5 = 60
  • “456” → 4×5×6 = 120
  • “567” → 5×6×7 = 210
  • “678” → 6×7×8 = 336
  • “789” → 7×8×9 = 504

最大乘积是504。

这个问题在以下领域有应用：

  1. 金融分析：计算连续时间段的最大收益
  2. 数据挖掘：寻找数据中的最大模式
  3. 算法竞赛：经典的滑动窗口问题
  4. 密码学：分析数字序列的特性

让我们先看看练习提供的结构和函数签名：

#[derive(Debug, PartialEq)]
pub enum Error {
    SpanTooLong,
    InvalidDigit(char),
}

pub fn lsp(string_digits: &str, span: usize) -> Result<u64, Error> {
    unimplemented!(
        "largest series product of a span of {} digits in {}",
        span,
        string_digits
    );
}

我们需要实现一个函数，计算数字字符串中指定长度连续子序列的最大乘积，并处理各种错误情况。

设计分析

1. 核心要求

  1. 输入验证：检查字符串是否只包含数字
  2. 长度检查：确保跨度不超过字符串长度
  3. 边界情况：处理跨度为0的特殊情况
  4. 数值计算：计算连续子序列的乘积
  5. 最大值查找：找到所有可能乘积中的最大值

2. 技术要点

  1. 滑动窗口算法：高效计算连续子序列
  2. 错误处理：使用Result类型处理各种错误
  3. 数值溢出：使用u64类型避免溢出
  4. 性能优化：避免重复计算

完整实现

1. 基础实现

#[derive(Debug, PartialEq)]
pub enum Error {
    SpanTooLong,
    InvalidDigit(char),
}

pub fn lsp(string_digits: &str, span: usize) -> Result<u64, Error> {
    // 处理跨度为0的特殊情况
    if span == 0 {
        return Ok(1);
    }
    
    // 检查跨度是否超过字符串长度
    if span > string_digits.len() {
        return Err(Error::SpanTooLong);
    }
    
    // 验证所有字符都是数字
    for c in string_digits.chars() {
        if !c.is_ascii_digit() {
            return Err(Error::InvalidDigit(c));
        }
    }
    
    // 计算最大乘积
    let digits: Vec<u64> = string_digits
        .chars()
        .map(|c| c.to_digit(10).unwrap() as u64)
        .collect();
    
    let mut max_product = 0;
    
    for window in digits.windows(span) {
        let product = window.iter().product();
        if product > max_product {
            max_product = product;
        }
    }
    
    Ok(max_product)
}

2. 优化实现（避免重复计算）

#[derive(Debug, PartialEq)]
pub enum Error {
    SpanTooLong,
    InvalidDigit(char),
}

pub fn lsp(string_digits: &str, span: usize) -> Result<u64, Error> {
    if span == 0 {
        return Ok(1);
    }
    
    if span > string_digits.len() {
        return Err(Error::SpanTooLong);
    }
    
    let digits: Vec<u64> = string_digits
        .chars()
        .map(|c| {
            c.to_digit(10)
                .map(|d| d as u64)
                .ok_or(Error::InvalidDigit(c))
        })
        .collect::<Result<Vec<u64>, Error>>()?;
    
    let mut max_product = 0;
    
    for window in digits.windows(span) {
        let product = window.iter().product();
        if product > max_product {
            max_product = product;
        }
    }
    
    Ok(max_product)
}

3. 高性能滑动窗口实现

#[derive(Debug, PartialEq)]
pub enum Error {
    SpanTooLong,
    InvalidDigit(char),
}

pub fn lsp(string_digits: &str, span: usize) -> Result<u64, Error> {
    if span == 0 {
        return Ok(1);
    }
    
    if span > string_digits.len() {
        return Err(Error::SpanTooLong);
    }
    
    // 验证并转换字符为数字
    let digits: Result<Vec<u64>, Error> = string_digits
        .chars()
        .map(|c| {
            c.to_digit(10)
                .map(|d| d as u64)
                .ok_or(Error::InvalidDigit(c))
        })
        .collect();
    
    let digits = digits?;
    
    // 使用滑动窗口计算最大乘积
    let mut max_product = 0;
    
    // 计算第一个窗口的乘积
    let first_product: u64 = digits[..span].iter().product();
    max_product = first_product;
    
    // 滑动窗口计算后续乘积
    let mut current_product = first_product;
    for i in span..digits.len() {
        // 除以窗口左边的元素，乘以新加入的元素
        if digits[i - span] != 0 {
            current_product /= digits[i - span];
            current_product *= digits[i];
        } else {
            // 如果除数为0，重新计算整个窗口的乘积
            current_product = digits[i - span + 1..=i].iter().product();
        }
        
        if current_product > max_product {
            max_product = current_product;
        }
    }
    
    Ok(max_product)
}

测试用例分析

通过查看测试用例，我们可以更好地理解需求：

#[test]
fn return_is_a_result() {
    assert!(lsp("29", 2).is_ok());
}

函数应该返回Result类型。

#[test]
fn find_the_largest_product_when_span_equals_length() {
    assert_eq!(Ok(18), lsp("29", 2));
}

当跨度等于字符串长度时，应该返回所有数字的乘积（2×9=18）。

#[test]
fn find_the_largest_product_of_two_with_numbers_in_order() {
    assert_eq!(Ok(72), lsp("0123456789", 2));
}

在有序数字中查找长度为2的最大乘积（8×9=72）。

#[test]
fn find_the_largest_product_of_three_with_numbers_in_order() {
    assert_eq!(Ok(504), lsp("0123456789", 3));
}

在有序数字中查找长度为3的最大乘积（7×8×9=504）。

#[test]
fn a_span_is_longer_than_number_is_an_error() {
    assert_eq!(Err(Error::SpanTooLong), lsp("123", 4));
}

当跨度超过字符串长度时，应该返回SpanTooLong错误。

#[test]
fn an_empty_string_and_no_span_returns_one() {
    assert_eq!(Ok(1), lsp("", 0));
}

空字符串且跨度为0时，应该返回1（空乘积的定义）。

#[test]
fn a_string_with_non_digits_is_an_error() {
    assert_eq!(Err(Error::InvalidDigit('a')), lsp("1234a5", 2));
}

包含非数字字符时，应该返回InvalidDigit错误。

性能优化版本

考虑性能的优化实现：

#[derive(Debug, PartialEq)]
pub enum Error {
    SpanTooLong,
    InvalidDigit(char),
}

pub fn lsp(string_digits: &str, span: usize) -> Result<u64, Error> {
    // 特殊情况：跨度为0
    if span == 0 {
        return Ok(1);
    }
    
    // 特殊情况：跨度超过长度
    if span > string_digits.len() {
        return Err(Error::SpanTooLong);
    }
    
    // 使用字节数组提高性能
    let bytes = string_digits.as_bytes();
    let mut digits = Vec::with_capacity(bytes.len());
    
    // 验证并转换为数字
    for &byte in bytes {
        if byte >= b'0' && byte <= b'9' {
            digits.push((byte - b'0') as u64);
        } else {
            // 找到无效字符并返回错误
            let invalid_char = byte as char;
            return Err(Error::InvalidDigit(invalid_char));
        }
    }
    
    // 特殊情况：如果任何数字是0，最大乘积可能是0
    let mut max_product = 0u64;
    
    // 使用滑动窗口
    for window in digits.windows(span) {
        // 如果窗口中包含0，乘积为0
        if window.contains(&0) {
            if max_product < 0 {
                max_product = 0;
            }
            continue;
        }
        
        // 计算窗口乘积
        let product = window.iter().product();
        if product > max_product {
            max_product = product;
        }
    }
    
    Ok(max_product)
}

// 进一步优化的版本
pub fn lsp_optimized(string_digits: &str, span: usize) -> Result<u64, Error> {
    if span == 0 {
        return Ok(1);
    }
    
    if span > string_digits.len() {
        return Err(Error::SpanTooLong);
    }
    
    // 预分配向量
    let mut digits = Vec::with_capacity(string_digits.len());
    
    // 验证并转换
    for c in string_digits.chars() {
        match c.to_digit(10) {
            Some(digit) => digits.push(digit as u64),
            None => return Err(Error::InvalidDigit(c)),
        }
    }
    
    // 如果跨度为1，直接返回最大数字
    if span == 1 {
        return Ok(*digits.iter().max().unwrap());
    }
    
    let mut max_product = 0u64;
    
    // 使用传统的滑动窗口方法
    for i in 0..=digits.len() - span {
        let mut product = 1u64;
        let mut has_zero = false;
        
        for j in 0..span {
            if digits[i + j] == 0 {
                has_zero = true;
                product = 0;
                break;
            }
            product *= digits[i + j];
        }
        
        if has_zero {
            if max_product < 0 {
                max_product = 0;
            }
        } else if product > max_product {
            max_product = product;
        }
    }
    
    Ok(max_product)
}

错误处理和边界情况

考虑更多边界情况的实现：

#[derive(Debug, PartialEq)]
pub enum Error {
    SpanTooLong,
    InvalidDigit(char),
}

#[derive(Debug, PartialEq)]
pub enum LspError {
    SpanExceedsLength,
    InvalidCharacter(char),
    NegativeSpan,
}

pub fn lsp(string_digits: &str, span: usize) -> Result<u64, Error> {
    // 处理负跨度的情况（usize不能为负，但我们可以检查其他情况）
    if span == 0 {
        return Ok(1); // 空乘积定义为1
    }
    
    if span > string_digits.len() {
        return Err(Error::SpanTooLong);
    }
    
    // 验证所有字符
    let digits: Result<Vec<u64>, Error> = string_digits
        .chars()
        .map(|c| {
            c.to_digit(10)
                .map(|d| d as u64)
                .ok_or(Error::InvalidDigit(c))
        })
        .collect();
    
    let digits = digits?;
    
    // 查找最大乘积
    let mut max_product = 0u64;
    
    for window in digits.windows(span) {
        let product = window.iter().product();
        if product > max_product {
            max_product = product;
        }
    }
    
    Ok(max_product)
}

// 带详细错误信息的版本
pub fn lsp_detailed(string_digits: &str, span: usize) -> Result<u64, LspError> {
    if span == 0 {
        return Ok(1);
    }
    
    if span > string_digits.len() {
        return Err(LspError::SpanExceedsLength);
    }
    
    let digits: Result<Vec<u64>, LspError> = string_digits
        .chars()
        .enumerate()
        .map(|(index, c)| {
            match c.to_digit(10) {
                Some(digit) => Ok(digit as u64),
                None => Err(LspError::InvalidCharacter(c)),
            }
        })
        .collect();
    
    let digits = digits?;
    
    let mut max_product = 0u64;
    
    for window in digits.windows(span) {
        let product = window.iter().product();
        if product > max_product {
            max_product = product;
        }
    }
    
    Ok(max_product)
}

扩展功能

基于基础实现，我们可以添加更多功能：

#[derive(Debug, PartialEq)]
pub enum Error {
    SpanTooLong,
    InvalidDigit(char),
}

pub struct LspCalculator;

impl LspCalculator {
    pub fn new() -> Self {
        LspCalculator
    }
    
    /// 计算最大序列乘积
    pub fn largest_series_product(&self, string_digits: &str, span: usize) -> Result<u64, Error> {
        lsp(string_digits, span)
    }
    
    /// 计算所有子序列乘积
    pub fn all_series_products(&self, string_digits: &str, span: usize) -> Result<Vec<u64>, Error> {
        if span == 0 {
            return Ok(vec![1]);
        }
        
        if span > string_digits.len() {
            return Err(Error::SpanTooLong);
        }
        
        let digits: Result<Vec<u64>, Error> = string_digits
            .chars()
            .map(|c| {
                c.to_digit(10)
                    .map(|d| d as u64)
                    .ok_or(Error::InvalidDigit(c))
            })
            .collect();
        
        let digits = digits?;
        
        let products: Vec<u64> = digits
            .windows(span)
            .map(|window| window.iter().product())
            .collect();
        
        Ok(products)
    }
    
    /// 查找产生最大乘积的子序列
    pub fn find_series_with_largest_product(&self, string_digits: &str, span: usize) -> Result<Option<String>, Error> {
        if span == 0 {
            return Ok(Some(String::new()));
        }
        
        if span > string_digits.len() {
            return Err(Error::SpanTooLong);
        }
        
        let digits: Result<Vec<u64>, Error> = string_digits
            .chars()
            .map(|c| {
                c.to_digit(10)
                    .map(|d| d as u64)
                    .ok_or(Error::InvalidDigit(c))
            })
            .collect();
        
        let digits = digits?;
        let mut max_product = 0u64;
        let mut best_series: Option<String> = None;
        
        for (i, window) in digits.windows(span).enumerate() {
            let product = window.iter().product();
            if product > max_product {
                max_product = product;
                let series: String = string_digits[i..i+span].to_string();
                best_series = Some(series);
            }
        }
        
        Ok(best_series)
    }
    
    /// 计算最小序列乘积
    pub fn smallest_series_product(&self, string_digits: &str, span: usize) -> Result<u64, Error> {
        if span == 0 {
            return Ok(1);
        }
        
        if span > string_digits.len() {
            return Err(Error::SpanTooLong);
        }
        
        let digits: Result<Vec<u64>, Error> = string_digits
            .chars()
            .map(|c| {
                c.to_digit(10)
                    .map(|d| d as u64)
                    .ok_or(Error::InvalidDigit(c))
            })
            .collect();
        
        let digits = digits?;
        
        let min_product = digits
            .windows(span)
            .map(|window| window.iter().product::<u64>())
            .min()
            .unwrap_or(0);
        
        Ok(min_product)
    }
    
    /// 获取乘积统计信息
    pub fn product_statistics(&self, string_digits: &str, span: usize) -> Result<ProductStatistics, Error> {
        let all_products = self.all_series_products(string_digits, span)?;
        
        if all_products.is_empty() {
            return Ok(ProductStatistics {
                count: 0,
                min: 0,
                max: 0,
                average: 0.0,
            });
        }
        
        let count = all_products.len();
        let min = *all_products.iter().min().unwrap();
        let max = *all_products.iter().max().unwrap();
        let sum: u64 = all_products.iter().sum();
        let average = sum as f64 / count as f64;
        
        Ok(ProductStatistics {
            count,
            min,
            max,
            average,
        })
    }
}

pub struct ProductStatistics {
    pub count: usize,
    pub min: u64,
    pub max: u64,
    pub average: f64,
}

pub fn lsp(string_digits: &str, span: usize) -> Result<u64, Error> {
    if span == 0 {
        return Ok(1);
    }
    
    if span > string_digits.len() {
        return Err(Error::SpanTooLong);
    }
    
    let digits: Result<Vec<u64>, Error> = string_digits
        .chars()
        .map(|c| {
            c.to_digit(10)
                .map(|d| d as u64)
                .ok_or(Error::InvalidDigit(c))
        })
        .collect();
    
    let digits = digits?;
    
    let mut max_product = 0u64;
    
    for window in digits.windows(span) {
        let product = window.iter().product();
        if product > max_product {
            max_product = product;
        }
    }
    
    Ok(max_product)
}

实际应用场景

Largest Series Product在实际开发中有以下应用：

  1. 金融分析：计算连续交易日的最大收益乘积
  2. 生物信息学：分析DNA序列中的模式
  3. 信号处理：检测信号中的峰值模式
  4. 游戏开发：实现得分计算和排行榜
  5. 数据挖掘：寻找时间序列中的最大增长模式
  6. 密码学：分析数字序列的统计特性
  7. 质量控制：检测生产过程中的异常模式
  8. 网络分析：分析流量数据中的峰值

算法复杂度分析

  1. 时间复杂度：O(n×m)

    • 其中n是字符串长度，m是跨度长度
    • 对于每个可能的窗口位置，需要计算m个数字的乘积

  2. 空间复杂度：O(n)

    • 需要存储转换后的数字数组

与其他实现方式的比较

// 使用递归的实现
pub fn lsp_recursive(string_digits: &str, span: usize) -> Result<u64, Error> {
    if span == 0 {
        return Ok(1);
    }
    
    if span > string_digits.len() {
        return Err(Error::SpanTooLong);
    }
    
    let digits: Result<Vec<u64>, Error> = string_digits
        .chars()
        .map(|c| {
            c.to_digit(10)
                .map(|d| d as u64)
                .ok_or(Error::InvalidDigit(c))
        })
        .collect();
    
    let digits = digits?;
    
    fn max_product_recursive(digits: &[u64], span: usize, index: usize) -> u64 {
        if index + span > digits.len() {
            0
        } else {
            let current_product: u64 = digits[index..index+span].iter().product();
            let rest_max = max_product_recursive(digits, span, index + 1);
            current_product.max(rest_max)
        }
    }
    
    Ok(max_product_recursive(&digits, span, 0))
}

// 使用函数式编程的实现
pub fn lsp_functional(string_digits: &str, span: usize) -> Result<u64, Error> {
    if span == 0 {
        return Ok(1);
    }
    
    if span > string_digits.len() {
        return Err(Error::SpanTooLong);
    }
    
    let digits: Result<Vec<u64>, Error> = string_digits
        .chars()
        .map(|c| {
            c.to_digit(10)
                .map(|d| d as u64)
                .ok_or(Error::InvalidDigit(c))
        })
        .collect();
    
    let digits = digits?;
    
    let max_product = digits
        .windows(span)
        .map(|window| window.iter().product::<u64>())
        .max()
        .unwrap_or(0);
    
    Ok(max_product)
}

// 使用迭代器链的实现
pub fn lsp_iterator_chain(string_digits: &str, span: usize) -> Result<u64, Error> {
    if span == 0 {
        return Ok(1);
    }
    
    match string_digits.len() {
        0 if span > 0 => return Err(Error::SpanTooLong),
        len if span > len => return Err(Error::SpanTooLong),
        _ => {}
    }
    
    string_digits
        .chars()
        .map(|c| c.to_digit(10).map(|d| d as u64).ok_or(Error::InvalidDigit(c)))
        .collect::<Result<Vec<u64>, Error>>()
        .map(|digits| {
            digits
                .windows(span)
                .map(|window| window.iter().product::<u64>())
                .max()
                .unwrap_or(1)
        })
}

总结

通过 largest-series-product 练习，我们学到了：

  1. 滑动窗口算法：掌握了经典的滑动窗口技术
  2. 错误处理：熟练使用Result类型处理各种错误情况
  3. 数值计算：学会了处理大数乘积和避免溢出
  4. 性能优化：了解了不同实现方式的性能特点
  5. 边界情况处理：学会了处理各种输入边界情况
  6. 迭代器使用：深入理解了Rust迭代器的强大功能

这些技能在实际开发中非常有用，特别是在处理时间序列分析、数据挖掘、算法优化等场景中。Largest Series Product虽然是一个具体的数学问题，但它涉及到了算法设计、错误处理、性能优化等许多核心概念，是学习Rust实用编程的良好起点。

通过这个练习，我们也看到了Rust在数值计算和算法实现方面的强大能力，以及如何用安全且高效的方式实现经典算法。这种结合了安全性和性能的语言特性正是Rust的魅力所在。

# rust # 开发语言 # 后端
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

教案和教学设计的区别是什么？90%的老师都搞混了

avatar AtomGit开源社区

如何使用向量库faiss和LLM判断问题是否被记录

在实际去重应用场景中，我们可能经常需要判断某个问题检查是否被记录。问题库规模可能很大，比如几千条记录，直接人工判断不太现实。这里基于网络资料，尝试直接用LLM以及基于相似性判断，探索高效准确的去重方案。

avatar AtomGit开源社区

新手也能上手 2026 降AI率平台测评：工具对比与推荐

2026年真正好用的AI论文降重与改写工具，核心看降重效果、去AI味、格式保留、学术适配四大指标。综合实测，千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是

avatar AtomGit开源社区