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

大子数组和（rust重拳出击）"/>

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

文章目录

• 53. 最大子数组和：
• • 样例 1：
  • 样例 2：
  • 样例 3：
  • 提示：
• 分析：
• 题解：
• • rust：
  • go：
  • c++：
  • python：
  • java：

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

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