算法leetcode｜53. 最大子数组和（rust重拳出击）

文章目录

53. 最大子数组和：

给你一个整数数组

nums

，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

样例 1：

输入：
    
    nums = [-2,1,-3,4,-1,2,1,-5,4]
    
输出：
    
    6
    
解释：
    
    连续子数组 [4,-1,2,1] 的和最大，为 6 。

样例 2：

输入：
    
    nums = [1]
    
输出：
    
    1

样例 3：

输入：
    
    nums = [5,4,-1,7,8]
    
输出：
    
    23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 刚开始以为要暴力破解，双循环什么的。
• 稍微思考一下，连续子数组，那么只需要考虑前面的情况。
• 抽象的问题往往难以理解，所以我们把问题想象成是连续存钱最多的金额，正数就是收入赚钱，负数就是支出花钱。
• 如果天天都是收入赚钱的，那么肯定是从头到尾加起来就是最多的。
• 如果天天都是支出花钱的，那么哪天花的最少，相当于存的最多。
• 事实上肯定是有正有负，不管是正是负，都没关系，因为我们可以从头再来，如果前几天存钱总金额是负数，那我们可以和自己说，算了，从今天开始重新计算吧，历史如果是负债累累，那么就重新开始计算啊，这样才容易打破历史记录。

题解：

rust：

implSolution{pubfnmax_sub_array(nums:Vec<i32>)->i32{let(mut pre,mut ans)=(0, nums[0]);
        nums.into_iter().for_each(|num|{
            pre = num.max(pre + num);
            ans = ans.max(pre);});return ans;}}

go：

funcmaxSubArray(nums []int)int{
    pre, ans :=0, nums[0]for_, num :=range nums {if pre >0{
            pre += num
        }else{
            pre = num
        }if pre > ans {
            ans = pre
        }}return ans
}

c++：

classSolution{public:intmaxSubArray(vector<int>& nums){int pre =0, ans = nums[0];for(int num: nums){
            pre =max(pre + num, num);
            ans =max(ans, pre);}return ans;}};

python：

classSolution:defmaxSubArray(self, nums: List[int])->int:
        pre, ans =0, nums[0]for num in nums:
            pre =max(pre + num, num)
            ans =max(ans, pre)return ans

java：

classSolution{publicintmaxSubArray(int[] nums){int pre =0, ans = nums[0];for(int num: nums){
            pre =Math.max(pre + num, num);
            ans =Math.max(ans, pre);}return ans;}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~