苏州大写的网站建设,北京社保网址,手机版网站案例,销售网站建设的意义【LetMeFly】1749.任意子数组和的绝对值的最大值
力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-absolute-sum-of-any-subarray/
给你一个整数数组 nums 。一个子数组 [numsl, numsl1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl numsl1 ... nums…【LetMeFly】1749.任意子数组和的绝对值的最大值
力扣题目链接https://leetcode.cn/problems/maximum-absolute-sum-of-any-subarray/
给你一个整数数组 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
方法一动态规划
首先想数组的最大子数组怎么求
遍历数组使用一个变量 M M M记录以当前元素结尾时的最大子数组。 M m a x ( n u m s [ i ] , M n u m s [ i ] ) M max(nums[i], M nums[i]) Mmax(nums[i],Mnums[i])
可以只选择当前元素也可以和前面的元素连起来。
接着想子数组的最大和绝对值怎么求 max ( a b s ( s u b a r r a y ) ) m a x ( m a x ( s u b a r r a y ) , − m i n ( s u b a r r a y ) ) \max(abs(subarray)) max(max(subarray), -min(subarray)) max(abs(subarray))max(max(subarray),−min(subarray))
最大的和的绝对值 要么等于 最大和 要么等于 最小和的相反数。
时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
class Solution {
public:int maxAbsoluteSum(vectorint nums) {int ans abs(nums[0]), m nums[0], M nums[0];for (int i 1; i nums.size(); i) {M max(nums[i], M nums[i]);m min(nums[i], m nums[i]);ans max(ans, max(M, -m));}return ans;}
};Python
# from typing import Listclass Solution:def maxAbsoluteSum(self, nums: List[int]) - int:ans, m, M abs(nums[0]), nums[0], nums[0]for i in range(1, len(nums)):M max(nums[i], M nums[i])m min(nums[i], m nums[i])ans max(ans, M, -m)return ans同步发文于CSDN原创不易转载请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/132158662
