您现在的位置是:首页 >其他 >算法leetcode|53. 最大子数组和(rust重拳出击)网站首页其他

算法leetcode|53. 最大子数组和(rust重拳出击)

二当家的白帽子 2024-07-11 18:01:02
简介算法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:

impl Solution {
    pub fn max_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:

func maxSubArray(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++:

class Solution {
public:
    int maxSubArray(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:

class Solution:
    def maxSubArray(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:

class Solution {
    public int maxSubArray(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/ 博客原创~


风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。