53. 最大子序和

每天一道Rust-LeetCode(2019-12-23)

坚持每天一道题,刷题学习Rust.

题目描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: ,
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

首先保存一个当前最大和
从前往后走的时候,碰到一个新的数值假定a[i]
那么计算sum=max(a[i],a[i]+sum),作为继续往下推进的条件.

解题过程

use std::cmp::max;

struct Solution {}
impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut max_sum = std::i64::MIN;
        let mut sum = std::i32::MIN as i64;
        for n in nums {
            sum = max(sum + n as i64, n as i64);
            //            println!("n={},sum={}", n, sum);
            if sum > max_sum {
                max_sum = sum;
            }
        }
        max_sum as i32
    }
}
#[cfg(test)]
mod test {
    use super::*;
    use crate::share::*;
    #[test]
    fn test() {
        let t = Solution::max_sub_array(vec![-2, 1, -3, 4, -1, 2, 1, -5, 4]);
        assert_eq!(t, 6);
    }
}

一点感悟

其他

欢迎关注我的github,本项目文章所有代码都可以找到.

xxxxxxxsgg dsgggg 本站总访问量 本站访客数人次