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/ 博客原创~