网站建设会议议程,网站建设方案评审,高端互联网推广,模板网站多少钱一个题目#xff1a;
链接#xff1a;LeetCode 1749. 任意子数组和的绝对值的最大值 难度#xff1a;中等
给你一个整数数组 nums 。一个子数组 [numsl, numsl1, …, numsr-1, numsr] 的 和的绝对值 为 abs(numsl numsl1 … numsr-1 numsr) 。
请你找出 nums 中 和的绝对…题目
链接LeetCode 1749. 任意子数组和的绝对值的最大值 难度中等
给你一个整数数组 nums 。一个子数组 [numsl, numsl1, …, numsr-1, numsr] 的 和的绝对值 为 abs(numsl numsl1 … numsr-1 numsr) 。
请你找出 nums 中 和的绝对值 最大的任意子数组可能为空并返回该 最大值 。
abs(x) 定义如下
如果 x 是负整数那么 abs(x) -x 。如果 x 是非负整数那么 abs(x) x 。
示例 1 输入nums [1,-3,2,3,-4] 输出5 解释子数组 [2,3] 和的绝对值最大为 abs(23) abs(5) 5 。 示例 2 输入nums [2,-5,1,-4,3,-2] 输出8 解释子数组 [-5,1,-4] 和的绝对值最大为 abs(-51-4) abs(-8) 8 。 提示
1 nums.length 105-104 nums[i] 104
前缀和
前缀和的最大值减最小值即为子数组和的绝对值最大值。
代码
class Solution {
public:int maxAbsoluteSum(vectorint nums) {int n nums.size();vectorint preSum(n 1);int minSum 0, maxSum 0;for(int i 1; i n; i) {preSum[i] preSum[i - 1] nums[i - 1];minSum min(minSum, preSum[i]);maxSum max(maxSum, preSum[i]);}return maxSum - minSum; // 前缀和最大值-最小值}
};时间复杂度O(N)。 空间复杂度O(N)。
