算法leetcode｜53. 最大子数组和（rust重拳出击）网站首页 其他

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

二当家的白帽子 2024-07-11 18:01:02

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

文章目录

53. 最大子数组和：
分析：
题解：

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴

分析：

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

题解：

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;
    }
}