企业门户网站管理办法,福州百度代理,郑州网站开发公司哪家好,河南省住房和城乡建设厅信息网目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
题目给我们一个数组#xff0c;让我们找出它的绝对值最大的子数组的和。
这边的子数组是要求连续的#xff0c;让我们找出一个元素之和…目录
题目
示例
分析
代码 题目 示例 分析
题目给我们一个数组让我们找出它的绝对值最大的子数组的和。
这边的子数组是要求连续的让我们找出一个元素之和的绝对值最大的连续子数组。
要绝对值最大那么就是两种情况最大的正数以及最小的负数所以我们可以兵分两路一次寻找正数的最大值一次寻找负数的最小值。
我们很容易就能想到使用滑动窗口右窗口滑动用来吸收新的数而左窗口滑动用来吐出不要的数。我们要使用滑动窗口就必须要搞清楚左窗口什么时候滑动滑动到什么时候停止。
我们先看看怎么寻找正数的最大值我们的右窗口一直往右扩张直到如果窗口内的总和为负数了那么目前为止的窗口总和就变成“累赘”了因为我们要的是寻找最大的正数一旦有负数了我们就把窗口全部丢弃从右窗口的右边再接着“滑动”。
那可能有人会问为什么是把窗口全部丢弃而不是开始滑动左窗口。
因为窗口的总和变为负数这一结果是右窗口吸收新元素造成的因此我们不需要的元素一定是靠近右窗口的如果开始滑动左窗口那么一开始滑出的只会是我们需要的正数总和只会越来越小直到左窗口和右窗口重叠窗口总和变成0然后再接着从右窗口的右边接着“滑动”。
大家可能发现了在本题中我们的左窗口没有存在的必要因为它不需要滑动每次更新都是直接更新到右窗口的位置所以我们只需要用一根指针来遍历原数组即可此外还需要用两个变量分别接收当前“窗口”内的正数最大值和我们已经获取到的正数的最大值。每次移动指针我们都判断当前“窗口”的总和有没有小于0小于0就抛弃掉当前窗口将窗口总和置为0重新开始“滑动”。
那我们说完了怎么获取正数的最大值还有一个就是要获取负数的最小值这个也是上面的步骤只不过是改变一下判断条件就是判断当前窗口的总和有没有大于0大于0就抛弃掉当前窗口将窗口总和置为0重新开始“滑动”。
上面两种可以同时进行只是各自需要两个变量来分别记录和更新。
最后再比较一下把正数的最大值和负的负数的最小值中最大的返回出去即可。 代码
class Solution {
public:int maxAbsoluteSum(vectorint nums) {int maxResabs(nums[0]),minResabs(nums[0]);int tempMax0,tempMin0;for(int num:nums){if(tempMaxnum0) tempMax0;else tempMaxnum;if(tempMinnum0) tempMin0;else tempMinnum;if(tempMinminRes) minRestempMin;if(tempMaxmaxRes) maxRestempMax;}return max(maxRes,-minRes);}
};
