算法leetcode｜53. 最大子数组和（rust重拳出击）-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法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 <= 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;
    }
}

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

到了这里，关于算法leetcode｜53. 最大子数组和（rust重拳出击）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！