当前位置：首页 > news >正文

力扣HOT100之普通数组：53. 最大子数组和

news 来源：原创 2025/7/22 7:23:38

这道题目我用贪心做的，感觉用贪心的思路比较简单，以后要是面试碰到这道题就直接用贪心好了，这道题用贪心的核心思想就是不断将数组元素i加入总和sum，如果sum比当前维护的最大值result更大，说明当前遍历到的i是正数，对于增大总和是有帮助的，直接更新result的值。否则就说明当前的i是负数，这里就需要进一步判断sum的大小，如果sum已经小于0，就说明sum对增大总和已经没有帮助了，直接将sum重置为0即可。
这是贪心的代码，还是挺简洁的。

class Solution {
public:int maxSubArray(vector<int>& nums) {//贪心解法int result = -INT_MAX;int sum = 0;for(int& i : nums){sum += i;if(sum > result) result = sum;  // i为正数，直接更新最大和// 若此时sum依然为负数，则对数值变大没有帮助，重置为0（丢弃）if(sum < 0) sum = 0;}return result;}
};

但是我看灵神解这道题是用前缀和和动态规划来解的，这里主要学习一下前缀和的解法，动态规划的解法在代码随想录里已经学习过了。感觉前缀和的解法也很通俗易懂欸！！
我们定义一个前缀表pre，其中pre[j] = nums[0] + nums[1] + nums[2] + ... + nums[j - 1]，这里我们依然定义pre[0] = 0，我们知道子数组的和可以转化为两个前缀和的差，例如，nums[i]到nums[j]的和可以转化为pre[j + 1] - pre[i],因此，我们可以先构造出一个前缀表，然后从下标1开始遍历，直到遍历结束，在从左往右遍历的过程中，用一个变量min_pre来记录当前的最小前缀，每遍历一个前缀和，我们就可以将其减去其左侧的最小前缀和，这样就能得到以第j - 1个元素为尾元素的子数组能取到的最大和，同时我们用一个变量result来维护当前的最大子数组和，就能计算出整个数组的最大子数组和。

class Solution {
public:int maxSubArray(vector<int>& nums) {//前缀和解法int result = INT_MIN;int min_pre = 0;  //维护最小前缀vector<int> pre(nums.size() + 1, 0);  //前缀表for(int i = 1; i < pre.size(); ++i)  //构造前缀表pre[i] = pre[i - 1] + nums[i - 1];for(int i = 1; i < pre.size(); ++i){ //遍历前缀表，计算最大子数组和result = max(result, pre[i] - min_pre);min_pre = min(min_pre, pre[i]);}return result;}
};

相关文章：