用 Rust 求子串绝对值最大

这两天学习了 rust 的语法

bookmark

尝试使用 rust 来写今天的 leetcode 的每日一题

https://leetcode.cn/problems/maximum-absolute-sum-of-any-subarray

给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。

请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。

边查文档边写的代码:

impl Solution {

    pub fn max_abs(a:i32,b:i32) -> i32 {

        if a <0{
            a= -a
        }
        if b<0{
            b= -b
        }

        if a > b {
            a     
        }else{
            b 
        }
    }

    pub fn max_absolute_sum(nums: Vec<i32>) -> i32 {
        let mut res = 0;

        let mut dp_max = vec![0;nums.length()];
        let mut dp_min = vec![0;nums.length()];
        
        for (i,num) in nums.iter().enumerate() {
            if i == 0 {
                dp_max[0] = *num
                dp_min[0] = *num 
                res = Solution::max_abs(dp_max[0],dp_min[0])
            }else{
                let max_num = dp_max[i-1] + *num
                if max_num > *num{
                    dp_max[i] = max_num
                }else{
                    dp_max[i] =*num
                }

                let min_num = dp_min[i-1] + *num
                if min_num < *num{
                    dp_min[i] = min_num
                }else{
                    dp_min[i] = *num
                }
                
                max_num = Solution::max_abs(dp_max[i],dp_min[i]) 
                res = Solution::max_abs(max_num,res)
            }
        }
        res
    }
}

编译错误提示

• 忘记写 ;

error: expected `;`, found `dp_min`
  --> src/main.rs:60:33
   |
60 |                 dp_max[0] = *num
   |                                 ^ help: add `;` here
61 |                 dp_min[0] = *num 
   |                 ------ unexpected token

• 获取数组长度 len 写成 length

|         let mut dp_max = vec![0;nums.length()];
|                                      ^^^^^^ help: there is a method with a similar name: `len`

• 未定义的结构体

34 | impl Solution {
   |      ^^^^^^^^ not found in this scope

• 最后的返回没有分号

pub fn max_absolute_sum(nums: Vec<i32>) -> i32 {
   |            ----------------                    ^^^ expected `i32`, found `()`
   |            |
   |            implicitly returns `()` as its body has no tail or `return` expression
...
87 |         res;
   |            - help: remove this semicolon to return this value

• 计算最大绝对值函数的所有权

pub fn max_absolute_sum(nums: Vec<i32>) -> i32 {
   |            ----------------                    ^^^ expected `i32`, found `()`
   |            |
   |            implicitly returns `()` as its body has no tail or `return` expression
...
87 |         res;
   |            - help: remove this semicolon to return this value

• 所有权只读

70 |                 let max_num = dp_max[i-1] + *num;
   |                     -------
   |                     |
   |                     first assignment to `max_num`
   |                     help: consider making this binding mutable: `mut max_num`
...
84 |                 max_num = Solution::max_abs(dp_max[i],dp_min[i]);
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot assign twice to immutable variable

修改的结果

struct Solution{

}


impl Solution {

    pub fn max_abs(a:i32,b:i32) -> i32 {
        let mut a = a ;
        let mut b = b ;
        if a <0{
            a= -a;
        }
        if b<0{
            b= -b;
        }

        if a > b {
            a     
        }else{
            b 
        }
    }

    pub fn max_absolute_sum(nums: Vec<i32>) -> i32 {
        let mut res = 0;

        let mut dp_max = vec![0;nums.len()];
        let mut dp_min = vec![0;nums.len()];
        
        for (i,num) in nums.iter().enumerate() {
            if i == 0 {
                dp_max[0] = *num;
                dp_min[0] = *num;
                res = Solution::max_abs(dp_max[0],dp_min[0])
            }else{
                let mut max_num = dp_max[i-1] + *num;
                if max_num > *num{
                    dp_max[i] = max_num;
                }else{
                    dp_max[i] =*num;
                }

                let min_num = dp_min[i-1] + *num;
                if min_num < *num{
                    dp_min[i] = min_num;
                }else{
                    dp_min[i] = *num;
                }
                
                max_num = Solution::max_abs(dp_max[i],dp_min[i]);
                res = Solution::max_abs(max_num,res);
            }
        }
        res
    }
}


fn main(){
    Solution::max_absolute_sum(vec![1,-3,2,3,-4]);
}

总结

参看其他人写的代码

• 直接使用 for i in 0..n 要比 nums.iter().enumerate() 要好一些
• 数值型函数本身有 max min abs 函数,不需要自己写.
• 计算时由于过程已经保存 dp 的结果也不用保存,只需要保存上一次的结果给下一次循环用即可.
• rust 的语法确实很难描述,需要大量的实践,特别是开始写的时候变量的传递有些懵.

最终版本:

//f(n) 绝对值最大 = n 的 最大值和最小值的绝对值取大
// f(n) 最大值 = f(n-1) 的最大值+n 和 n 取大
// f(n) 最小值 = f(n-1) 的最小值+n  和 n 取小

impl Solution {
    pub fn max_absolute_sum(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = 0;

        let mut dp_max = 0;
        let mut dp_min = 0;
        
        for i  in 0..n {
            if i == 0 {
                dp_max = nums[0];
                dp_min = nums[0]; 
                res = dp_max.abs().max(dp_min.abs());
            }else{
                
                let  max_num = dp_max + nums[i];
                dp_max = max_num.max(nums[i]); 

                let  min_num = dp_min + nums[i];
                dp_min = min_num.min(nums[i]); 
                
                res = res.max(dp_max.abs().max(dp_min.abs())); 

            }
        } 
        res
    }
}