LeetCode热题100——53.最大子数组和（题解+答案+要点）

张开发
• 2026/4/15 14:23:38 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

LeetCode热题100——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^5-10^4 nums[i] 10^4题解1.核心思想动态规划从左到右扫描时时刻维护一个“当前子数组”并决定如果加上当前数字能让子数组变大就加上如果加上反而变小就丢掉前面的从当前数字重新开始。同时每走一步都记录下目前为止见到的最大和。2.核心代码pre max(pre x, x); maxAns max(maxAns, pre);pre表示以当前元素结尾的连续子数组的最大和。注意必须包含当前元素maxAns表示全局最大和初始设为数组的第一个元素不能设为 0详见下文的要点。答案class Solution { public: int maxSubArray(vectorint nums) { int pre0; int maxAnsnums[0]; for(int i0;inums.size();i){ premax(prenums[i],nums[i]); maxAnsmax(maxAns,pre); } return maxAns; } };要点1.为什么maxAns初始为nums[0]而不是 0如果数组全是负数比如[-5, -2, -1]最大子数组和应该是-1。但是如果maxAns初始为 0那么max(0, -5) 0会错误地返回 0。

更多文章