leetcode(88)_1749_medium_任意子数组和的绝对值的最大值_python

任意子数组和的绝对值的最大值

题目描述:
给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, …, numsr-1, numsr] 的和的绝对值 为 abs(numsl + numsl+1 + … + numsr-1 + numsr) 。
请你找出 nums 中 和的绝对值 最大的任意子数组(可能为空),并返回该 最大值 。
abs(x) 定义如下:
如果 x 是负整数,那么 abs(x) = -x 。
如果 x 是非负整数,那么 abs(x) = x 。
示例 :
输入:nums = [1,-3,2,3,-4]
输出:5
解释:子数组 [2,3] 和的绝对值最大,为 abs(2+3) = abs(5) = 5 。
提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

解法

一个直接的思路是统计各个子数组连加和的最大值(要大于0)与最小值(要小于0),如此再取绝对值最大就行了。以最大值为例,如果当前连加和小于0了,那说明前面的元素对于后面的元素来说是累赘,就直接弃掉,重新从0开始记录连加和。
当然,另外一种思路是计算出来前缀和,然后统计前缀和的最大最小值,相减就是极差。

代码
class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        sum1, sum2, max_sum = 0, 0, 0
        for num in nums:
            sum1 += num
            sum2 += num
            if sum1 <= 0:
                sum1 = 0
            if sum2 >= 0:
                sum2 = 0
            max_sum = max(sum1, -sum2, max_sum)
        return max_sum
      
测试结果

执行用时:112 ms, 在所有 Python3 提交中击败了 54.64% 的用户
内存消耗:25.1 MB, 在所有 Python3 提交中击败了 54.64% 的用户

说明

算法题来源:力扣(LeetCode)

上一篇:【UMI】路由懒加载


下一篇:redis(四)----发布订阅